Skip to main content

Full text of "Classification of trees and applications of topology and graph theory to neurosurgery"

See other formats


A CLASSIFICATION OF TREES AND 
APPLICATIONS OF TOPOLOGY AND GRAPH THEORY TO 

NEUROSURGERY 



By 

TAE-IL YI 



.sf^'^MTw^-.^f 



, -, '. f 

A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL 

OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT 

OF THE REQUIREMENTS FOR THE DEGREE OF 

DOCTOR OF PHILOSOPHY 



UNIVERSITY OF FLORIDA 



2000 



■ ■" .^ 



t-^^ ? 



HH"''--^* iX 



^ , , V- 



Copyright 2000 



by 



TAE-IL YI 



■I r'> 



TO 

My parents, Beom-Young Sz Bong-Wol, 

who show me how to love, 

My wife, Moon-Sil, 

who shows me what is love, 

and 

My children, David & Peter, 

who are the reasons why I love 



ACKNOWLEDGEMENTS 

I would like to express my sincere appreciation to the members of my supervi- 
sory committee, Dr. Beverly Brechner, Dr. Philip Boyland, Dr. James Keesling, Dr. 
Li-Chien Shen, and Dr. Mary Kantowski, for their patience, knowledge, concern, and 
especially for showing me how to study and teach. I would especially like to thank 
my advisor, Dr. Beverly Brechner, who accepted me and gave me a chance to work 
with her. I also want to express my appreciation for all her effort and all that she has 
done for me, not only in my major field, but also in my life. I would like to thank 
Matthew Harvey who brought me some wonderful ideas and wrote the Mathematica 
programs. I would like to thank Dr. Francis Bova who brought me these questions 
which were 'new world' to me. 1 would like to thank Dr. Meeks for helpful conver- 
sations, and Dr. Thomas Wagner who gave me the information about neurosurgery 
that I did not know before. I would like to thank Dr. Yunmei Chen who gave me 
inspiration. I would like to thank Dr. Miklos Bona who showed me some insights of 
combinatorics. Finally, I would like to thank the Department of Mathematics that 
allowed me to be here and meet all these wonderful people. 



IV 



TABLE OF CONTENTS 



ACKNOWLEDGEMENTS iv 

ABSTRACT vii 

CHAPTERS 

1 INTRODUCTION 1 

2 AN AUTOMATED SPHERE PACKING PLAN FOR BRAIN TUMORS 5 

2.1 Introduction 5 

2.2 Linac 5 

2.3 Procedure of Radiosurgery 6 

2.4 Making a Sphere by Arcs of Beams 10 

2.5 Sphere Packing Plan 10 

2.6 ShelHng Algorithm 15 

3 A CLASSIFICATION OF UNLABELED TREES 25 

3.1 Introduction 25 

3.2 Definitions 26 

3.3 Vertex Sequence 28 

3.4 Degree Sequence 36 

3.5 Perfect Sequence and Main Theorem 44 

3.6 Obtaining Perfect Sequences 45 

3.7 Extended Partitions and the Algorithm 53 

4 TREES AS INVARIANTS FOR BRAIN TUMOR SHAPES 59 

4.1 Introduction 59 

4.2 Definitions and Some Properties 60 

4.3 Graphs for Sphere Packing Plans 64 

4.4 Order in the Vertex Set 65 

4.5 Maximal Tree from a Graph 71 

4.6 Graph from a Maximal Tree 81 

4.7 Algorithm for Our Maximal Tree 81 



APPENDICES 

A SHELLING PROGRAM FOR SPHERE PACKING 82 

A.l Program for Data Reading 82 

A. 2 Program for Center Searching 83 

B PROGRAM FOR THE MAXIMAL TREE OF A GRAPH 91 

C PROGRAM FOR CLASSIFYING TREES BY SEQUENCES 93 

C.l Program 93 

C.2 Some Program Results 97 

D LABELED GRAPHS AND TREES 102 

D.l Number of Labeled Graphs and Labeled Trees 102 

D.2 Sketch of the Construction of a Priifer-code 102 

D.3 Reconstruction of a Tree from a Priifer-code 103 

REFERENCES 105 

BIOGRAPHICAL SKETCH 105 



VI 



Abstract of Dissertation Presented to the Graduate School 

of the University of Florida in Partial Fulfillment of the 

Requirements for the Degree of Doctor of Philosophy 



- •#■ 



' A CLASSIFICATION OF TREES AND 
APPLICATIONS OF TOPOLOGY AND GRAPH THEORY TO 

NEUROSURGERY 

By 

Tae-Il Yi 
August 2000 

Chairman: Dr. Beverly L. Brechner 
Major Department: Mathematics 

The work of this dissertation was motivated by our work with a medical group 

at the Brain Institute at the University of Florida. This group was led by Dr. Francis 

Bova, who raised the following questions: 

(1) Can you automate the time-consuming sphere packing process for our "multiple 
isocenters method of stereographic radiosurgery" for brain tumors? (This surgery is 
noninvasive, radiation surgery to destroy brain tumors.) 

(2) Can you classify the shapes of brain tumors? 

In this dissertation, we construct some algorithms and programs to (partially) 
answer these questions. Our major (joint) results are described below. 

Our first result is an algorithm and a program that produce a unique sphere 
packing plan for any given brain tumor shape, filling the shape with different size 
spheres in a unique way. This process automates the 'sphere packing' part of the 



vn 



surgery plan. Additional code by the medical group was necessary to allow for physi- 
cian input in certain critical cases. It was then possible for the medical group to 
incorporate this into their surgery plan, semi-automating it, and significantly reduc- 
ing the surgeons' surgery planning time. 

Our second result is a complete classification of unlabeled n-trees. We assign 
to each n-tree, a sequence of n nonnegative integers satisfying certain properties; and 
from each such sequence, we can recover the n-tree assigned to it. In fact, we present 
both an algorithm and code to produce not only the sequences, but also pictures of 

if. 

the corresponding trees. - . -^ • i 

Our final result is a first attempt at a topological classification of tumor shapes. 
We first use our sphere packing plan to construct a graph representing the tumor. 
We then have an algorithm and program which uniquely select a maximal tree in the 
graph. Thus we can assign a unique tree to each tumor shape. However, different 
graphs may produce the same tree. Our tree classification allows us to compare 
two tumor shapes very easily, by just looking at their corresponding sequences. In 
particular, different sequences come from different sphere packing plans, but the 
converse does not hold. 



Vlll 



CHAPTER 1 
INTRODUCTION 

The work of this dissertation was motivated by two questions raised by Dr. 
Francis Bova, of the Brain Institute, Shands Hospital, and the Department of Neuro- 
surgery, all at the University of Florida. It turns out the different-sounding questions 
are very much related and are tied together naturally in this thesis. In fact, our 
results for the second question depend upon our results for the first question. Dr. 
Bova led a medical group, which joined with our mathematics group, for a number 
of discussions over a two year period. This resulted, for us, in both a joint medical 
paper [11] and in this dissertation. We also want to reference the dissertation [10] of 
Thomas Wagner, Dr. Bova's medical physics student, who worked with us. 

We expect to have three mathematics publications from this dissertation-from 
Chapters 2, 3, and 4, respectively. The paper resulting from Chapter 2 will be joint 
with Professor Beverly Brechner, Professor Yunmei Chen, and Dr. Thomas Wagner. 
The papers resulting from Chapters 3 and 4 will be joint with Matthew Harvey, an 
undergraduate student working with Professor James Keesling on his honors thesis. 
Further, we anticipate an additional paper, to be joint with Yunmei Chen and her 
student. Dr. Stacey Chastain. This anticipated work will be an analysis of the tumor 
shapes of approximately 1000 interesting tumor radiation surgeries done by Bova and 
his colleagues at the University of Florida. 

Dr. Bova's questions were the following: 

1. Is it possible to automate the medical group's "multiple isocenters method of 
stereographic radiosurgery" to destroy brain tumors? 

2. Is it possible to classify brain tumor shapes? 



In this dissertation, we develop some algorithms and programs related to these 
questions. In stereographic radiosurgery, which is noninvasive surgery, radiation is de- 
Uvered by means of coUimators-cylindrical metal tubes, with cylindrical holes through 
them, through which the radiation flows. The goal of stereotactic radiosurgery for a 
brain tumor is to deliver the desired dosage to the target, and only the target. This 
is not possible in reality. So they do the next best thing, which is to deliver enough 
dosage to the target, to avoid as much normal tissue as possible, and to deliver as 
little radiation as possible to whatever normal tissue must be affected. There are two 
additional important criteria-dose homogeneity and dose conformality. That is, we 
do not want 'hot spots,' which have been experimentally determined to cause com- 
plications; and we do want rapid falloff of dose levels outside the actual tumor. One 
of several such radiation surgery methods is called the 'Multiple Isocenter Method.' 
This involves filling the tumor image with spheres of different sizes, until the image is 
best filled up. In this dissertation, we call such a plan, a 'Sphere Packing Treatment 
Plan.' 

In Chapter 2, we develop both an algorithm, which is called a 'shelling process' 
(or 'grassfire process' in medical terminology), and a C-R- program to identify the 
centers and sizes of spheres for this sphere packing treatment plan. For any given 
brain tumor, our program gives us a unique sphere packing plan. This sphere packing 
plan can be represented numerically as a list of parameters of the spheres, namely 
the centers and radii of the spheres. Based on this algorithm, the medical group 
developed a proprietary program for an automated sphere packing treatment plan, 
including dosage distribution, and other things (see Wagner et al.[ll]). Since this 
program always produces the same plan for the same tumor, it can be used as a 
'benchmark' against which to compare other treatment plans. 

In Chapter 3, we obtain a code to denote an unlabeled tree by a unique, 
ordered, nonnegative integer sequence satisfying certain properties. We call such 



sequences, perfect sequences. That is, we obtain a complete classification of unlabeled 
n-trees by means of the perfect sequences of n nonnegative integers. Thus we have our 
main theorem of this chapter, the Tree Classification Theorem, (Theorem 3.5.5): For 
any positive integer n, let Tin) be the set of unlabeled n-trees and V{n) the set of 
perfect sequences of n-trees. Then there is a one-to-one correspondence between T{n) 
and V{n). We show how to assign a perfect sequence to a given tree, and conversely, 
how to reconstruct a tree from a given perfect sequence. We also include an algorithm 
and a Mathematica program to produce not only all the perfect n-sequences, for any 
given positive integer n > 3, but also pictures of the corresponding trees. By means of 
this program, we get our classification of unlabeled n-trees and also the total number 
of n-trees. 

In Chapter 4, we make a first attempt at a topological shape classification of 
tumors-actually of the sphere packing plan associated with the tumor shape. We first 
assign to each tumor a unique graph, and from that, we determine a unique tree. We 
obtain the graph by assigning a vertex for each sphere, and an edge between each pair 
of vertices representing adjacent spheres. This produces a unique connected graph 
corresponding to each sphere packing plan. Then, by using the notion of cutvertex, we 
give an order to the vertex set. We then use this order to build a unique maximal tree 
contained in the graph. Next, we develop an algorithm and a Mathematica program 
to assign a unique tree to each sphere packing plan. This program produces a list of 
edges of the tree, making it clear which edges are incident. 

Using our results of Chapter 3, we can now assign exactly one perfect sequence 
to each tumor. However, it may happen that more than one tumor shape (or graph) 
gives rise to the same tree, and therefore to the same perfect sequence. Thus, we do 
not yet have a real classification of tumor shapes. However, if two perfect sequences 
are distinct, then their corresponding trees, and therefore their respective correspond- 
ing graphs and sphere packing plans, are also distinct. Therefore we may consider 



their shapes to be distinct. Thus, we have our main result of Chapter 4, Theorem 
4.5.6: The perfect sequences are invariants of the shapes of arbitrary brain tumors. 
That is, if two brain tumors are represented by distinct perfect sequences, then their 
corresponding trees are not isomorphic, and therefore their respective graphs and 
sphere packing plans are not isomorphic. Thus, we may consider their shapes to be 
distinct. 

We refer the reader to Douglas[l], Gross[3], and Harary[5] for graph theory. 
We also refer the reader to Hall [4], Riordan[7] and Stanley [9] for combinatorics. 






CHAPTER 2 
AN AUTOMATED SPHERE PACKING PLAN FOR BRAIN TUMORS 

2.1 Introduction 

The goal of stereotactic radiosurgery for a brain tumor is to deliver the desired 
dosage to the target, and only the target. This is not possible in reality. So they do 
the next best thing, which is to deliver enough dosage to the target, to avoid as much 
normal tissue as possible, and to deliver as little radiation as possible to whatever 
normal tissue must be affected. There are two additional important criteria-dose 
homogeneity and dose conformality. That is, we do not want 'hot spots,' which 
have been experimentally determined to cause complications; and we do want rapid 
falloff of dose levels outside the actual tumor. One of several such radiation surgery 
methods is called the 'Multiple Isocenter Method.' This involves filling the tumor 
image with spheres of different sizes, until the image is best filled up. This noninvasive 
method of surgery, namely by using radiation, relies on a piece of equipment called the 
Linear Accelerator (or simply, Linac). In this chapter, we show how to automate the 
construction of a sphere packing plan for the tumor image. Most of the information 
in this chapter about treatment of a brain tumor is taken from Friedman et al.[2]. 
See [2] for further reference. 

2.2 Linac 

According to Friedman et al.[2], the linear accelerator is a complex machine 
capable of producing X-rays. A large amount of energy is generated by the power 
supply, which then powers the filament shown. This causes electrons to be emitted 
by the filament, which are in turn accelerated to higher energies using a (microwave) 



wave guide. The electrons are then changed in direction by the magnet so that they 
impact on a heavy metal alloy target. This results in X-ray production that can then 
be coUimated or shaped by both primary and secondary collimators within the linear 
accelerator head. This beam is further coUimated for radiosurgery by the tertiary 
radiosurgery collimator. (See Figure 2-1 and Figure 2-2.) 

The Linac is mounted on a rotating gantry such that the beam has a center of 
rotation about 1.5m above the floor. Usually, the isocenter accuracy is defined within 
a 2mm sphere. Because stereotactic radiosurgery depends on optimized accuracy, an 
improved system was designed at the University of Florida, by adding a set of bearings 
to the stereotactic collimator system and under the patient table. As a result, this 
new system achieves mechanical accuracy within 0.2mm±0.1mm for defining the 
treatment isocenter of beam delivery. 

The tertiary collimators are generally circular and allow improved centering 
of the treatment beam. The sizes of these collimators are from 5 to 40mm in 2- to 
5-mm increments. 

2.3 Procedure of Radiosurgery 

The procedure of radiosurgery is separated into 5 steps as follows. 

(1) Head ring attachment 

(2) CT scan 

(3) Image Processing 

(4) Planning 

(5) Treatment delivery 

For more detailed information, refer to Friedman et al.[2]. 

(1) Head ring attachment •; ^ -': ■ ,' > j ^ ^/^- -'5 j 

The stereotactic radiosurgery treatment requires attachment of a stereotactic 
head ring. This ring provides accurate information about the position and the shape 



Filament Waveguide 



Electron beam 



Power supply 





iH-iHI-f+l-H- 



(I^^M^£& 



mnnnmiBixumnrnmil^ 




Magnet 



' Heavy alloy target 



Primary (Internal) 
collimators 

Rattening filter 



Secondary (Adjustable) 
collimators 

Tertiary (Radiosurgery) 
collimators 

Photon tieam tor 
radiosurgery 



Floor stand with treatntent arm atxjve 



"> ." 



Figure 2-1. System of Linac (Friedman et al.[2]) 




Figure 2-2. Operation of Linac (Friedman et al.[2]) 



of brain tumors from the computer tomography (CT). This ring also helps to insure 
that the treatment target is accurately placed at the precise isocenter of the Linac. 

(2) CT scan 

After attaching the head ring, a series of cut filming is taken. Eighty to 150 
CT slices are taken per patient. For radiosurgical treatment planning, getting the 
accurate size and shape of the target is very important. Underestimation of the target 
size may result in treatment failure. Overestimation of size results in the inclusion of 
normal brain tissue within the treatment volume. Misrepresentation of an irregular 
target shape may lead to radiation damage of normal brain tissue. The accuracy 
of CT scanning depends on the size of the pixels that make up the scan image. 
The lateral and AP accuracy of scanning is approximately 0.6mm. But the axial 
dimension is determined by slice thickness of the CT scan, which is 1mm in general. 
The physicians use the so-called Brown-Roberts- Wells coordinates-or, simply BRW 
coordinates-which are called lateral (Lat), anterior-posterior (AP), and axial (Ax) 
coordinates. These are the x, y, and z coordinates, respectively. The direction of 
the lateral coordinate is from the left hand side ear to the right hand side ear of the 
patient. So the lateral view (or sagittal) is similar to the side view of the head, that 
is, views of shces along the lateral axis. This is the same as yz-plane views. The 
direction of the AP coordinate is from the back side of the head to the face. So the 
AP view (or coronal) is similar with the front view of the head, that is, views of slices 
along the AP axis. This is the same as xz-plane views. The direction of the axial (or 
vertical) coordinate is from the neck to the top of the head. So the axial view (or 
trans-axial) is similar to the sky view of the head, that is, views of slices along the 
axial axis. This is the same as xy-plane views. (See Figure 2-4.) 

(3) Image Processing 

An MRI scan has been done the day before surgery. Using a mouselike device, 
the CT and MRI images are transferred to the computer screen and fused. Then, 



10 

using geometric equations, the computer determines the lateral, AP, and vertical 
stereotactic coordinates of each point in each CT slice. 

(4) Planning 

Physicians use a mouse and their own judgment to 'eyeball' the location and 
the size of spheres for the treatment plan. 

(5) Treatment delivery 

The geometric sphere packing plan, developed as in (4), is combined with a 
proprietary dose planning program, and the resulting treatment plan is delivered by 
the Linac. 

2.4 Making a Sphere by Arcs of Beams 

By varying the angle of the gantry and the angle of the table, one can deliver 
a radiation beam to the target from any angle within the range of the rotation. The 
shape of the common intersection of an arc of beams passing through one isocenter is 
a sphere. The neurosurgeons deliver a series of arcs (usually 5 or 9 arcs) to produce 
a single isocentered sphere shape. For an ellipsoidal target, they use fewer numbers 
of arcs to make a single isocentered ellipsoid shape. (See Figure 2-3, 2-4 and 2-5.) 

So, if the target shape is very close to a sphere or an ellipsoid, then the 
treatment plan is relatively easy compared to an irregularly shaped target. In that 
case, we need to create a geometric treatment plan. 

2.5 Sphere Packing Plan 

As seen in the previous section, the physicians know how to irradiate-to- 
(eventually)destroy tumors which are shaped like spheres or ellipsoids. For a non- 
spherical shape of tumor, they try to fill the target with several spheres of different 
sizes. This is called the 'sphere packing' treatment plan. 

After finding a sphere packing plan, they treat each sphere separately as de- 
scribed in the previous section. So, multiple isocenter radiosurgery planning includes 



11 




Figure 2-3. One isocenter plan with five arcs of radiation (Wagner et al.[ll]) 



i 



12 



(270') 



(ago") 



(70') 






I H G FED C BA 

Figure 2-4. One isocenter plan with nine arcs of radiation (Friedman et al.[2]) 



13 



TARGET 



^ ^ z> ^ ^ 

*N<^.. V \ ', V ' / ' // ,- » *V \\ \ > 



-^<^> \^^0.'' !/'/'/ '-''-' 





















<^ 



B 


^ -CJ, T? ,J> ;^ : , <3 "^ ^ . 




^>~''->x\\ii^'.-/;.-;!^ ^>-;\\ /;'-^:5^ 






TARGET 


'''■■^'V^f^■^^;" '//■■'"•>■•'' 



Figure 2-5. Plan for a sphere shape and an ellipsoidal shape (Friedman et al.[2]) 



14 

the problem of determining the best sphere packing arrangement with which to fill 
the target volume. General methods for this treatment plan are iteratively based, 
dosimetrically driven algorithms. But these methods require many computations in 
order to compute a radiosurgical plan dose distribution, and then to evaluate the 
quality of the dose distribution. So geometrically based radiosurgery optimization 
has been suggested as a possible alternative means. 

However the method the physicians choose relies on human decisions and 
experience. Thus, for the same target, different surgeons may produce different plans. 
Even the same surgeon, doing the plan twice for the same target, may produce 
different plans. And the planning takes a long time, especially for a complicated 
target which needs more than 10 spheres. It might take as much as two hours of 
planning for a difficult case which needs about 20 spheres. During that time, the 
patient has to wait with the head ring attached to his or her head. And most 
importantly, even after spending the time to make a plan, many physicians without 
sufficient experience, are not sure if the plan is a 'good' one. 

Therefore, we provide an automated sphere packing method for the treatment 
plan (see Wagner et al.[ll]). This method shows potential to significantly aid the 
planning of difficult multiple isocenter cases. Based on tests with irregularly shaped 
phantom targets and with a representative sampling of clinical example cases, the 
method demonstrates the ability to generate radiosurgery plans comparable to, or 
of better quality than, multiple isocenter Linac radiosurgery plans found in other 
literature. At the same time, this program always produces the same treatment plan 
for the same tumor shape. So it can be used as a 'benchmark' to compare with other 
plans for the given tumor shape. Moreover, this program provides the treatment 
plan in a relatively short time. For a very difficult case which needed more than 18 
spheres, this program took less than 3 minutes instead of more than the 1.5 hours 



,15 

which were needed when the physicians created the plan using traditional methods. 
The algorithm of this program is shown in Figure 2-6. 

In the following section, we explain the 'shelling algorithm' which we used in 
this program to get the centers and sizes of spheres for the sphere packing plan. 

2.6 Shelling Algorithm 

The shelling procedure is best illustrated in Figure 2-7 to 2-16. The major 
steps of this shelling procedure are as follows. 
(1) Transferring the data of the boundary of the target 

From the CT scan, each point which is identified from the target contour data 
file can be mapped into a three dimensional array, since each CT scan shows the 
trans-axial view for a specific axial coordinate value. In the three dimensional array, 
we assign the lateral-, AP- and axial-coordinates to be x-, y- and z-axes, respectively. 
For each individual case, there are minimum and maximum values for x, y and z- 
axes. We assume the minimum value is always one. We get this information from 
the Program for Data Reading. (See Appendix A.l.) 

Let the target be minimally enclosed in an x-range beginning with one and 
ending with Mj,, a y-range beginning with one and ending with My, and a z-range 
beginning with one and ending with M^. Now we put 'safe bumper' layers sur- 
rounding the target. That is, we enlarge the box containing the target to ET = 
[0, M:, + l]x [0, My + l]x [0, M, + l]. ET stands for 'enlarged target box.' We assume 
that the dimension of each voxel is 1x1x1. Then we will number the voxels in a lexi- 
cographic manner, beginning with and ending with {Mj:+l)x{My + l)x{M^ + l) — l, 
giving us a total of (M^ -|- 1) x (M^ -|- 1) x (Mj -f 1) voxels with which we will work. 

Now we want to identify the voxels in ET in two different ways: first, by a set 
of coordinates {a, 6, c), and second, by an integer representing a counting procedure. 
Here, a is the left hand endpoint of the x-value of that voxel, b is the left hand 



Ui' '.. ?..,..- : w^-f rvLH 



■« V 



16 

endpoint of the y- value of that voxel, and c is the left hand endpoint of the z- 
value of that voxel. The second notation for the voxel (a,6,c) is by some integer 
n. The voxels are counted, using a lexicographic ordering beginning with and 
ending with {M^ + 1) x {My + I) x (M^ + 1) - 1 which is denoted by nofdata in 
the program (see Appendix A. 2). Then the voxel denoted by {a,b,c) is numbered 
as c X (Mj; + 1) X {My + 1) + a X {My + 1) + b. And it is clear that, for every 
< i < nofdata, there are unique nonnegative integers, a,b,c, such that i = 
c X (M:, + 1) X (My + 1) + a X {My + I) + b. That is, for every < z < nofdata, 
one and only one voxel is assigned. Note that Figure 2-7 to Figure 2-14 show the 
same trans-axial view at different stages of the algorithm. Thus these figures show 
the data of a fixed axial-coordinate value. 

(2) Assign a status value for each voxel 

For every < i < nofdata, the status value for the i-th. voxel is denoted 
by cc[i]. That is, we denote the status value for the voxel with coordinates {a,b,c), 
by cc\i] where i = ex {M^ + I) x {My + I) + a x {My + I) + b. The following is 
the procedure to assign status values. First of all, let cc[i] = —3 for every < 
i < nofdata. Then we assign the number, —1, as the status value for each voxel 
corresponding to any of the target contour data. Next, for every < j < Mj, we 
assign cc[j x{M:, + l)x{My + l)] = 0, because the j x (M^ -h 1) x (My -h l)-th voxel 
is the voxel at the left lower corner for every j-th trans-axial view; that is, the voxel 
belongs to the healthy tissue. (See Figure 2-8.) 

For each voxel with cc[i] = —3, we define cc[i] = if any of cc[i — 1], cc[i + 
1], cc[i — (My -I- 1)], cc[i -t- (My -h 1)] is 0. Note that this method produces zeros for 
every voxel in the safe bumper layers. (See Figure 2-9.) 

(3) Shelling the target voxels 

We proceed by mathematical induction on j, for 

'1 



' 0<J< 



X min{M^, My, M^} 



17 

For i = to {M^ + 1) X {My + 1) x (M, + 1) - 1, if the i-th voxel is assigned -1 
or -3 for its status value, and if any of cc[i - 1], cc[i + 1], cc[i - {My + 1)], cc[i + 
{My + 1)], cc[i - {M, + 1) X {My + 1)], cc[i + {M, + 1) X {My + 1)] is equal to j, 
then we assign a new status value for the i-th voxel as c[i] = j + 1. Note that Figure 
2-7 to Figure 2-14 show only a two-dimensional figure. But this procedure is held 
in a three-dimensional array. This process is repeated until the deepest lying voxels 
have been identified. The deepest lying voxel in the entire target volume would be 
the best location for an isocenter. And at the same time, the status value assigned to 
the deepest voxel indicates the radius of the sphere, which is one less than the status 
value of the voxel. This completes our induction. (See Figure 2-10.) 
(4) Removing the largest sphere 

At this moment, we might have several different voxels which have the same 
largest status value. So we choose the smallest numbered voxel as the center of the 
first largest sphere to be removed from the target. But in the program in Wagner et 
al.[ll], we choose the most effective voxel to be the center of the first largest sphere, 
by using the 'score function' which was developed by Tom Wagner. We think of 
the resulting sphere in the tumor as 'removed,' and therefore we can assign the new 
status value zero for these voxels in the sphere. To determine which voxels form the 
sphere that is removed, we do the following: Let R = voxel at the center of sphere 
to be removed. Let r = status value of R. Then we remove all voxels S with the 
property that distance(center of R, center of S) < r - 1. (See Figures 2-11 and 2-12.) 

Now, we proceed by mathematical induction on j, for 

< J < - X min{Mj;, My, MJ . 

For i = to (M^ -|- 1) x {My + I) x (M^ -|- 1) - 1, if the i-th voxel has status value 
> j, we reassign a new status value as follows: if any of cc[i — 1], cc[i + 1], cc[i — 
(My + 1)], cc[i + {My + l)], cc[i-{M^ + l)x{My + l)], cc[i + {M, + l)x{My + l)] is 
equal to j, then we assign a new status value for the i-th voxel as c[i] = j + 1. This 



18 

process is repeated until the deepest lying voxels have been identified. (See Figures 
2-13 to 2-15.) 

And we repeat step (4) until we get either or 1 for the status value of each 
voxel in ET, the enlarged target box. Because the smallest size of the diameter of 
collimators is 5mm, we finish our program when the status values of all the voxels are 
zeros and/or ones. (See Figure 2-16.) The remaining part will be taken care of by 
the 'score function' (see Wagner et al.[ll]). After finishing this procedure, we have 
the spheres filling the target. In Figure 2-17, we see the sphere packing plan within 
a target by this method. 

For further detailed information about the score function and the automated 
sphere packing plan, we refer the reader to Wagner et al.[ll] and Wagner[10]. 



f START 








' 


' 






Build 3D voxel 
model of target 




Grassfire 

procedure 
(shelling) 








i 


L 




Reset non-coverec 




target voxels to "1" 




values 




i 


k 










— Yes — 



Evaluate score for 

maximum valued 

voxels 



Select voxel with 

maximum score as 

seed voxel 



Locate max score 

in neighborhood o) 
seed voxel 



Place sphere 




Figure 2-6. Sphere packing algorithm block diagram (Wagner et al.[ll]) 





19 


y 

10 
5 




































































< 


• 


• 


• 


• 


• 


• 




























• 


« 


• 


» < 


)• 












<•• 


» 


4 


• 


• 














« 


























• 


• 




• 


• 












• 


• 




































• 










« 






































• 


• 
















































• 


• 






• 








































• 


• 






• 


• 






































• 










9 


































• 


• 


• 










• 


• 


• 


• 








• 


• 














• 


• 
























• 


• 


» 


• 




• 


» 


• 


• 


• 


• 










































• 


• 






































































5 10 15 20 -> X 
Figure 2-7. Transferring the data of the boundary of the target 






-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 




-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-1 


-1 


-1 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-1 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-1 


-1 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-3 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


■*■ 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-3 


-3 


-3 


-3 


~1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-3 


-3 


-3 




-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-3 


-3 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 




-1 


-3 


-3 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 




-3 


-3 


-3 


-3 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-1 


-3 


-3 


-3 


-3 


-1 


-1 


-1 


-1 


-3 


-3 


-3 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-1 


-1 


-3 


-1 


-1 


-1 


-1 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 





-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 




Figure 2-8. Status values for the boundary and the initial voxel 

■'■■■ ■' a ; .; ijv ,^*. > ,. • , :^. 







20 



































































































-1 


-1 


-1 


-1 


-1 


-1 


-1 









































-1 


-1 


-1 


-1 


-1 


-3 


-3 


"3 


-3 


-3 


-1 


-1 


-1 


-1 


-1 


-1 























-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-3 


-1 


-1 

















-1 


1 


"3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


~3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 














-1 


-3 


-3 


-3 


-3 


-3 


"3 


-3 


-3 


-3 


"3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 











-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 








-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 








-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 














-1 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 


-1 














-1 


-1 


-1 


-1 


-3 


-3 


-3 


-1 


-1 


-3 


-3 


-3 


-3 


-3 


-3 


-1 


-1 



































-1 


-1 


-1 


-1 





-1 


-1 


-1 


-1 


-1 


-1 






























































-1 


-1 







































































































Figure 2-9. Status values for the normal voxels 





































































































1 


1 


1 


1 


1 


1 


1 









































1 


1 


1 


1 


1 


2 


2 


2 


2 


2 


1 


1 


1 


1 


1 


1 























1 


2 


2 


2 


2 


2 


3 


3 


3 


3 


3 


2 


2 


1 


1 


2 


1 


1 



















1 


2 


3 


3 


3 


3 , 4 


4 


4 


4 


4 


3 


3 


2 


2 


3 


2 


2 


1 
















2 


3 


4 


4 


4 


4 " fi 5 


f) : i) 


5 


4 ; 4 3 


3 


4 


3 


2 


1 















2 


3 


4 


i) : S 


5 ^ i) 


5 BSia i> ^ [j U 1 i) 4; 


^1 


2 




1 










2 


3 


4 


4 


5 i) 


:j ^ '1 : 4 ;> 


i) 


i) f) h o 4 


4 


3 


2 




1 










1 


2 


3 


3 


4 


4 


4 


3 


3 


4 


4 


4 


4 


4 


4 


3 


3 


2 
1 


2 
















1 


2 


2 


2 


3 


3 


3 


2 


2 


3 


3 


3 


3 


3 


3 


2 


2 


1 
















1 


1 


1 


1 


2 


2 


2 


1 


1 


2 


2 


2 


2 


2 


2 


1 


1 



































1 


1 


1 


1 





1 


1 


1 


1 


1 


1 






























































1 


1 







































































































Figure 2-10. Sh 


lelli 


ng 


the 

r 

■■■■ i. 


tai 


rgel 


, vo 


xels 











21 
































































































1 


1 


1 


1 


1 


1 


1 










































1 


1 


1 


1 


1 


2 


2 


2 


2 


1:2. 


1 


1 


1 


1 


1 


1 




















1 


2 


2 


2 


2 


2 


3 


3 


3 


3 


3 
4 


2 


2 


1 


1 


2 


1 


1 



















1 


2 


3 


3 


3 


3 


4 


4 


4 


4 


3 


3 


2 


•A 


3 


2 


2 


1 
















2 


3 


4 


4 


4 


4 


5 


5 


5 


5 


5 


4 


4 


3 


3 


4 


3 


2 


1 















2 


3 


4 


5 


5 


5 


6 


5 


5 


6 


6 


.if 


•1 4 


5 


4 


3 


2 


1 


1 










2 


3 


4 


4 


5 


5 


5 


4 


4 


5 


5 


V^5 


i 

i) 5 


1 


4 


3 


2 




1 










1 


2 


3 


3 


4 


4 


4 


3 


3 


4 


4 


4 4 


4 


4 


3 


3 


2 


2 
















1 


2 


2 


2 


3 


3 


3 


2 


2 


3 


3 


3 


3 


3 


3 


2 


2 


1 


1 
















1 


1 


1 


1 


2 


2 


2 


1 


1 


2 


2 


2 


2 


2 


2 


1 


1 



































1 


1 


1 


1 





1 


1 


1 


1 


1 


1 






























































1 


1 




































































































Figure 2-11. Choosing the largest sphere 
































































































1 





1 


1 


1 


1 


1 









































1 


1 























*2^ 


1 


1 


1 


1 


1 


1 























1 


2 





























2 


2 


1 


1 


2 


1 


1 



















1 


2 





























3 


3 


2 


2 


3 


2 


2 


1 
















2 


3^ 





























4 

3- 


4 


3 


3 


4 


3 


2 


1 















2 



































h 


^4 4 


f) 1 


3 


2 




1 










2 


3 





























I 


r 




1 


4 


3 


2 




1 










1 


2 





























4 


4 


4 4 


3 


3 


2 


2 
















1 


2 





























3 


3 


3 


3 


2 


2 


1 


1 
















1 


1 


1 























2 


2 


2 


2 


2 


1 


1 



































1 


1 





1 





1 


1 


1 


1 


1 


1 






























































1 


1 






































































































Figure 2-12. Removing the largest sphere 



•,' * 






W- 



•'^X' 



22 j 

■ , ■ i 












































































1 
1 

: 

■ 























1 





1 


1 


1 


1 













































1 























1 




1 


1 


1 


1 


1 























1 

































2 


1 


1 


2 


1 


1 



















2 

































2 


2 


2 


3 


2 


2 


1 
















2 

































2 


3 


3 


4 


3 


2 


1 















1 

































1 


2 


3 


4 


4 


3 


2 




1 










2 

































2 


3 


4 


4 


4 


3 


2 




1 











2 

































2 


3 


4 


3 


3 


2 


2 













1 

































2 


3 


3 


2 


2 


1 


1 
















1 




1 























1 


2 


2 


2 


2 


1 


1 



































1 


1 





1 





1 


1 


2 


2 


1 


1 































































1 


1 




































































































Figure 2-13. Shelling the remaining target voxels 

































































































1 





1 


1 


1 


1 













































1 























1 




1 


1 


1 


1 


1 























1 

































2 


1 


1 


2 


1 


1 



















2 

































2 


2 


2 


3 


2 


2 


1 
















2 

































2 


3 


3 


4 


3 


2 


1 















1 

































1 


2 


3 


4 


4 


3 


2 




1 










2 

































2 


3 


4 


4 


4 


J. 


2 




1 










2 

































2 


3 


4 


3 


3 


2 


2 
















1 

































2 


3 


3 


2 


2 


1 


1 
















1 




1 























1 


2 


2 


2 


2 


1 


1 



































1 


1 





1 





1 


1 


2 


2 


1 


1 






























































1 


1 







































































































Figure 2-14. Choosing the largest sphere of the remaining target 





2 


3 .i 

J 

i 

i 

] 

! 

■ 

































































































1 





1 


1 


1 


1 


1 











































1 























1 


1 


1 


1 


1 


1 


1 























1 































1 


2 


1 


1 


2 


1 


1 



















2 































1 


r 


2 


1 


■ T 


2 


2 


1 
















2 































1 


1 


1 





1 


1 


2 


1 















1 

















































1 


2 




1 










2 































1 

















1 


2 




1 










2 




















































1 
















1 































1 

















1 


1 
















1 




1 























1 


1 


















































1 


1 





1 





1 


1 


2 


1 


1 

































































1 


1 







































































































Figure 2-15. Removing the second sphere 


1 
i 

J 



































































































1 





1 


1 


1 


1 


1 









































1 


1 























1 


1 


1 


1 


1 


1 


1 























1 


1 





























1 





1 


1 





1 


1 

















1 





1 


















































1 


















































1 





1 

















1 











1 



























































1 


1 








1 





1 





























1 


























1 




































































1 

















1 





























1 

















1 


1 


1 














1 


1 


1 























1 





















































1 


1 





1 





1 











1 




































































1 





































































































Figure 2-16. Removing all the spheres 

"' ,.5 





24 



patB.vol 




Figure 2-17. A sphere packing plan for a brain tumor (Wagner et al.[ll]) 






*w>- 



CHAPTER 3 
A CLASSIFICATION OF UNLABELED TREES 

3.1 Introduction 

In this chapter, we obtain a code to denote an unlabeled tree. By means 
of this code, we classify unlabeled n-trees. One may take an unlabeled n-tree to 
be the geometric realization of a connected, finite, simplicial complex without any 
simple closed curves. In particular, we call a tree an n-tree if and only if it is a tree 
with n vertices (that is, (n - 1) edges). Our code assigns a unique, ordered, 'perfect 
sequence', pf{T) = (c?i,o?2, • • • ,c^„) , to each unlabeled n-tree, T. And, conversely, 
given an ordered sequence of n integers satisfying certain properties, it is the perfect 
sequence of exactly one unlabeled n-tree. Thus, we have our main theorem, the Tree 
Classification Theorem (Theorem 3.5.5). We then show how to reconstruct the tree 
shape from a given perfect sequence, by hand. 

Our work includes an algorithm and a Mathematica program (see Appendix 
C.l) that produce a fist of all the perfect sequences for all possible n-trees, thus also 
producing the number of n-trees, for any given n. For some examples, see Appendix 
C.2. Since our algorithm and program are based upon our main theorem, we know 
that all possible unlabeled n-trees are produced by the program. Thus the program 
gives us, for each positive integer n, a complete list of all unlabeled n-trees. 

Given n > 0, with sufficient computer power and time, our program will 
list all the unlabeled n-trees, thus telling us how many unlabeled n-trees there are. 
However, we do not have a simple formula that tells us how many unlabeled n-trees 
there are. This remains an open problem. 






25 



26 

The Literature contains work regarding the classification of labeled graphs 
and labeled trees. In Lovasz[6], the Priifer-code is used to determine the number of 
labeled n-trees (see the Appendix D.2 and D.3). In Sloane[8], Sloane shows a table 
for n < 26. However, Sloane references Harary for the method he uses. In Harary[5], 
there is a simple formula for the total number of labeled graphs with n vertices (see the 
Appendix D.l). There is also a formula for the total number of unlabeled n-trees, but 
it requires knowing the number of roo^et/ n-trees, which is calculated inductively. And, 
even though Harary[5] contains n-tree shapes up to n = 10, there is no explanation 
of how to get the shapes of these trees, while our work does show how to get these 
tree shapes from our code. 

This chapter is organized as follows: 

Section!: Introduction 

Section 2: Definitions 

Section 3: Vertex Sequence 

Section 4: Degree Sequence 

Section 5: Perfect Sequence and Main Theorem 

Section 6: Obtaining Perfect Sequences 

Section 7: Extended Partition and the Algorithm 

' 3.2 Definitions 

Most of the necessary definitions in this section are from Harary [5]. We refer 
the reader to Harary [5] for easy reference. 

Definition 3.2.1 A graph G = {V{G), E{G)) consists of a vertex set V[G) = 
{fi,. . .,u„} and an edge set E{G) = {ei,. ..,6™} C {{u,v}\u,v e V{G)} in which 
each edge is an unordered pair of two distinct vertices u and u, and the edge {u,u} 
is said to join u and v. For an edge {u,v} we say that u and v are adjacent 
vertices and the vertex u and the edge {u, v} are incident with each other, as are 

* .« ' -A r J - ' 



'Jt 



27 

V and {u,v}. From now on, \V{G)\ denotes the number of vertices and \E{G)\ 
denotes the number of edges. For a vertex u € V{G), the vertex set 

A{u) = {v E G\v is an adjacent vertex of u} 
is called the adjacent set of u. Note that u ^ A{u). 

Definition 3.2.2 A walk is an alternating sequence (uo, ei,Ui, 62, . . . ,6^, Ufc) of 
vertices and edges s.t. t;,_i 7^ u, for i = 1,2, ...,A;, and e,- = {vi-i,Vi} for i = 
1, 2, . . . , fc. If there is no confusion, a walk can be denoted by a sequence of vertices 
only in the path Hke (^1,^2, ...,Vk). A cycle is a walk (uq, Ci, Ui, 62, . . • , e/t, Vk) with 
k > 3 in which Vq = Vk is the only vertex repeated. A path is a walk with no 
repeated vertex. A {u,v)-path is a path with the first vertex u and the last vertex 
V. The length of the (u,u)-path, l{u,v), in a graph is the number of edges in the 
(u,u)-path. The distance d{u,v) between two vertices u and v is the length of a 
shortest path joining them, if any; otherwise d{u,v) = 00. Note that d{u,u) = 0. A 
graph G is connected iff every pair of vertices are joined by a path. A graph having 
no cycle is acyclic. Note that an acyclic graph can be disconnected. A forest is an 
acyclic graph. A tree is a connected acyclic graph. An n-tree is a tree with n vertices. 
Definition 3.2.3 We say that a graph G is isomorphic to a graph H if and only 
if there exists a bijection / : V{G) -)■ V{H) such that {u,v} € E{G) if and only if 
{f{u)J{v)} e E{H). 

Definition 3.2.4 An unlabeled tree is an isomorphism class of trees. 

We are interested in the total number of unlabeled n-trees and their shapes. 
For example, T^ = ({1,2, 3}, {{1, 2}, {2,3}}) and n = ({1,2,3}, {{2, 1}, {1,3}}) 
are different trees, but there is an isomorphism / : V{Ti) -^ ^(^2) by /(I) = 
2, /(2) = 1, /(3) = 3. Thus they are the same unlabeled tree, so we want to count 
them as one unlabeled 3-tree. From now on, a tree implies an unlabeled tree unless 
otherwise specified. 



28 

Definition 3.2.5 The degree of a vertex u, defined by d{v), is the sum of the 
number of edges incident with v. A vertex v is called an endvertex if d{v) = 1. 

We will use the geometric, that is, topological realization of a graph inter- 
changeably with 'graph' as defined above. 
Proposition 3.2.6 [5] The following statements are equivalent for a graph T : 

(1) T is a tree. . ^ . 

(2) Every two vertices of T are joined by a unique path. 

(3) T is connected and \V[T)\ = \E{T)\ + 1. 

(4) T is acyclic and \V(T)\ = \E{T)\ + 1. 

Note that there are exactly n vertices and n-1 edges in an n-tree. 
Proposition 3.2.7 (Degree sum formula) [5] // G is a graph with the vertex 
degrees (/i,...,(/„, then Y^y^v(G)'^i = '^\^i^)\- 
Corollary 3.2.8 For an n-Tree T we have 

T^l, d{iH) = 2{n - 1) = 2\E{T)\ = 2{\V{T)\ - 1) 
where Vi is a vertex of T for i = 1,2, . . . ,n. 

Because a nontrivial tree satisfies Ylvev(T)^i'^) ~ 2|i^(T)| = 2(|V(T')| — 1), 
there are at least two vertices with degree 1. Thus we have the following theorem as 
a corollary. 

Theorem 3.2.9 [5] Every nontrivial tree has at least two endvertices. 

3.3 Vertex Sequence 

In this section, we define the vertex sequence of a given n-tree. 

Definition 3.3.1 Let T = {V, E) be an n-tree. If d{v) = m, then there are m 
components of T — {v}. A branch of v (or simply a v-branch) is a subtree which 
is the closure of a component of T — {v}. We call the set of vertices in a u-branch 
a v-branch vertex set. If w 6 A{v), then the u-branch vertex set containing u is 
called the {v,u)-branch vertex set and denoted by B{v,u) (or B{u)). We call the 



29 

set B'{v,u) = B{v,u) - {v} the {v,u)-subbranch vertex set, which is denoted by 

B'{u) if there is no confusion. The subtree consisting of B'{v,u) as the vertex set 

and {{s,t} e B'{v,u) x B'{v,u)\ {s,t} G E{T)} as the edge set is called the {v,u)- 

subhranch. 

Example 3.3.2 Let T be the 10-tree shown below. 



♦ « 



♦ < 



* '^ 



w 



X 



y 

Figure 3-1 

Since d{v) = 4, there are 4 components of T — {v}. Since A{v) = {r, i,u;,j/}, 
we have that 



B{v,r) = {t;,r,5,g,p}, 
B{v,t) = {v,t}, 
B{v,w) — {v,y;,u,.r}, 
B{v,y) = {v,y}, 



B'{v,r) = {r,s,q,p} 
B'{v,t)^{t} 
B'(v,w) = {w,u,x} 
B'{v,y) = {y}. 



On the other hand, we have that 

B{r,v) = {r,v,t,u,w,x,y}. 
That is, B{v, r) / B{r, v). And this is true for any tree except the 2-tree. In fact, for 
every n-tree with n > 2, there are at least 3 vertices, namely u,v, and w. Without 
loss of generality, let u and v be vertices adjacent to each other, and let the {w,v)- 
path contain the vertex u. Then w € B{v,u) and w B{u,v). 

Definition 3.3.3 A section of a sequence is a subsequence consisting of consecutive 
terms of the sequence. 

Definition 3.3.4 Let T = {V, E) be an n-tree with V = {x^Xi, . . . ,Xn}. We define 
the set, S, of sequences of the form s = (ui,f2) ■ ■ • ,^^n) , where 5 is a permutation 
of the Xi''s in V{T), to be those sequences satisfying: 



30 

(*) for any Vj with 1 < j < n, Uj+i € A{vk) - {ui, f2, • • • , Vj} 

where k = max{i G {l,2,...,i}| A{v,) - {vi,V2, . . . ,Vj} ^ 0}. 
Then S is called the vertex sequence set of T and each element, s, in S is called a 
vertex sequence of T. . 

Definition 3.3.5 For any u 6 V, we call Sy = {s e S\vi ^ v} C S the v-vertex 
sequence set. 

Definition 3.3.4 requires that the vertices in a sequence be listed in a particular 
way. The condition (*) ensures that all vertices are listed and that each is hsted 
exactly once. We can choose any vertex for the first term, Vi. Then the condition 
(*) says that, for the (i+l)-th term, we have to choose an unUsted adjacent vertex 
of Vi, if possible. If every adjacent vertex of u, is already used, then look backward 
along the sequence until we come to the first vertex which has an unused adjacent 
vertex. Then, for the (i+l)-th term, we assign one of the unused adjacent vertices of 
that vertex. To get a vertex sequence, we continue this procedure inductively. 
Note that every vertex sequence of an n-tree has n entries. 

Example 3.3.6 We show how to construct a vertex sequence of a given tree. Let 
T be the 7-tree shown below. 

t/ 



abode 
Figure 3-2 

Since we have freedom to choose the first term, let vi = b. Then V2 G A{vi) — 
{vi} = A{b) — {6} = {a, c, /} — {6} = {a, c, /} = A{b) = A{vi). So V2 must be one of 
the elements of A{vi) = A{b) = {a,c,f}. Let V2 = c. Since v^ G ^(^2) — {^^1,^2} = 
A{c) — {b,c} = {b,d,g} — {6, c} = {d,g}, v^ must be either d or g. Let ^3 = g. 
Then V4 A{v3) - {ui,U2,U3}, since ^(^3) - {ui,U2,U3} = {c} - {b,c,g} = 0. On 



31 

the other hand, we have that ^(^2) - {vi,V2,V3} = {b,d,g} - {b,c,g} = {d} ^ 0. 
Therefore we have to choose d as U4. Then U5 = e since A{v^ — {^1,^2, ^3,^4} = 
{c, e} — {6, c,^, (/} = {e}. Since we have 

^(us) - {ui,U2,^^3,^^4,U5} = {d} - {h,c,g,d,e\ =0, 
A(y^) - {vx,V2,V2„Vi,v^} = {c,e} -{6,0,5-, d,e} = 0^ 

A(U3) -{ui,U2,i^3,^^4,U5} = {c} -{6, c, (/,«?, e} =0, 

A{v2) - {vx,V2,V'i,v^,v^} = {h,g,d}- {h,c,g,d,e) =0, and 
Aiyx) - {vuV2, i'3, U4, ^^5} = {a, c, /} - {6, c, ^r, (/, e} = {a, /}, 

^6 must be either a or /. Let v% — f. Then we have that 

A{ve) - {ui, U2, V3, W4, U5, ue} = {b} - {6, c, g, d, e, /} = 0, 

A{v5) - {vi,V2,vz,V4,V5,ve} = {d} - {b,c,g,d,e,f} =0, 

^(^4) - {ui,U2,^'3,^^4,^^5,t^6} = {c,e} - {b,c,g,d,e,f} ^^, 

A{v2,) - {vi,V2,Vz,Vi,Vz,Ve] = {c} - {6, c, 5, c/, e, /} =0, 

A{v2) - {vi,V2,V2„Vi,Vz,v&] = {b,g,d} - {b,c,g,d,ej} =0, and 

A(ui) - {vi,V2,'y3,^^4,^^5,^^6} = {a,c,f}-{b,c,g,d,ej} = {a}. 

Therefore vr must be a; that is, we construct a vertex sequence 

{vi,V2,...,V7) = (6, c, ^r, (f, e, /, a) . 

For a given tree we will get different vertex sequences if we choose different 
vertices whenever we have two or more choices. But the sequence t = (6, c, d, e, /, a, g) 
cannot be a vertex sequence of T above. In fact, we have V5 = f. But we have that 

A{v4)- {vi,V2,V3,V4} = {d} - {b,c,d,e} =0, 

A{v3) - {ui, U2, V3, U4} = {c, e} - {6, c, d, e} = 0, 

A(t;2) - {^1,^2,^3,^4} = {b,d,g} - {b,c,d,e} = {g}, and 

A{vi) - {vi,V2,V3,V4} = {a,c,f}-{b,c,d,e} ={a,f}. 

That is, the sequence t has /, one of the elements of A{vi) — {vi,V2.,V3,V4}, for V5 

instead of g which is an element of A{v2) — {^1,^2, i'3,i^4}- It is a contradiction to 

the maximality of k in the definition of vertex sequence. 

Proposition 3.3.7 Let (ui, ^2, • • • , ^n) be a vertex sequence of an n-tree T. For any 
Vj with j > 1 there is unique 1 < k < j such that Vj G A{vk) — {ui, V2, . . . ., Vj-i}. 

Proof First of all, for any j > 1, we have Vj ^ v^ for i = 1,2, . . . , j — 1 from the 
Definition 3.3.4. Assume that there is j > 1 such that 

{vj, Vj+u- ■ ■ , t'n} n {{UiZlA{Vi)) U {^1, ^2, . . . , t^,-i}) = 0. 



32 

Then, for any u G {uj,Uj+i, . . . , v„} and any w € [UJZlAivi)) U {ui, V2, • • • , Vj}, 
there is no (■u,u;)-path in T. That is, T is not connected. It is a contradiction 
to the connectedness of a tree. Therefore there is I < k < j such that Vj 6 
A{vk) - {vi,V2,...,Vj-i}. If there are 1 < A;i < ^2 < j such that Vj e A{vki) - 
{vi,V2,...,Vj_i} and Uj € ^(ufcj - {vi, ^2, . . . ,Uj-i}, then the two edges, {vj^Vk^} 
and {fjjUfcj}, are elements of E{T). There is a path between Vk^ and Vk^ in the 
subtree {{vuV2, . . . ,Vj_i}, E'} where E' = {{u,v} E E{T)\u,v e {vuV2, ■ ■ ■ ,Vj.i}}. 
The tree T contains a cycle consisting of {vj,Vk^}, {vj^Vk^} and the (t;fci,t;fc2)-path. 
This contradicts the fact that a tree is acyclic. Therefore there is only one I < k < j 
such that Vj € A{vk) — {fi, ^2, • • • , ^j-i}- -L 

From the Definition 3.3.4 and the previous lemma we get the following corol- 
lary immediately. 
Corollary 3.3.8 Let {vi,V2,....,Vn) be a vertex sequence of an n-tree. Then 

(1) V2 € A{vi) . . ■■ 

(2) If d{vj) > 2 for any j = 2, 3, . . . , n — 1, then Vj^i G A{vj). 

(3) For any j = 2, 3, . . . , n — 1 if d{vj) — 1 and there is i < j such that d{vi) > 3 
and d{vk) = 2 for every A: = i + l,i + 2, . . . , j — 1, then Uj+i G A[vi) and Uj+i 
A{vp), for every p= 1,2,..., i- I, i + I,... J. 

Proposition 3.3.9 Let {vi, V2, . . . , Vn) he a vertex sequence of an n-tree and A[vi) = 
{vi^,Vi^,. . . ,Ui„} with 1 < li < I2 < . . . < Im- Then 

{t;i,t;2,...,u„} = U™i5(ui,ui.). 

Proposition 3.3.10 Let s = {vi,V2, ■ . . ,Vn) he a vertex sequence of a given n-tree 
T. If d{vj) = m for some j > 1, then there exist m vertices, Vi,Vj^,Vj^,...,Vj^_^ 
such that A{vj) = {r;,-, v^^ ,Vj^,..., Vj^_^ } with i< j < ji < J2 < ■ ■ ■ < jm-i ■ 
Proof For any j > 1 there exists unique i < j such that {vi,Vj} G E{T) 
by Proposition 3.3.7; that is, Vi G A{vj). So, for any Vk G A{vj) — {uj, j < k. 



33 

Since d{vj) - m, there are m - 1 vertices, Uii,^i2? • • • ) ^im-n such that A{vj) = 
{ui, Uj, , t;j2 , . . . , Uj„_, } with i<3 <n<J2< ■■■< jm-i- -L 

Proposition 3.3.11 Let s = (ui,U2, . . . , u„) 6e a vertex sequence of a given n-tree 
T. Let d{vi) = m and A{vi) = {uij, Ui^, . . . , ui^} be the adjacent set of Ui, named 
so that 1 < li < I2 < . . . < Im- Then, for any z = 1, 2, . . . , m, the set of vertices in 
the subbranch, fi'(ui, Ui,), forms a section in s starting with Vi^. 
Proof Clearly, the section containing uij starts with uij = ^2- Let B'(i'i,ViJ = 
{uijjUij+i, . . . ,uii+mi}. Assume that there is a vertex u E: V{T) — B'{vi,Vi^) such 
that (ujjjUij+i,. . .,?;ij+j,u, . . .) is a section of J. Since u ^ B'{vi^vi^), A{vi^j^k) — 
B'(vi, uij = for any k = 0, 1, 2, ... ,j from the definition. Thus ^i-oA{vl^+k) — 
B'{vi,vi^) = ^. That is, U;[.^oA(i'ii+fc) D ^'(^1, ^^i,)- On the other hand, A{vi^+k) C 
B'{vl,Vl^) forevery A; = 0, 1,2, . . . , j. Thus we have that U^=oA(uii+fc) C 5'(fi,Uii). 
Therefore U^=o^(^ii+*:) = B'{vi,vi^). That is, j = mi. Hence B'{vi,viJ forms 
a section in s. Since B'{vi,vi^) is a subbranch of Ui, Uij+mj-i-i ^ ^(m) for any 
u e B'{vi,vi^). Thus Vl^+rnl+l € A(ui). That is, vi^+rn,+i = vi^. For any i = 
1,2, ...,m — 1, let B'(vi,Vi-) form a section in s and Ui,^.m,+i = t^i.+i- By a simi- 
lar method, B'(vi,Vi^^^) forms a section in s and Ui,^.i+TOi+i+i = ^i,+2- -L 

The section formed by a subbranch i?'(?;i,ui,) is denoted by (B'(ui,UiJ). 
From the previous proposition, we have the following corollaries. 

Corollary 3.3.12 Let s = {vi,V2, . . . ,Vn) be a vertex sequence of a given n-tree 
T. Let d{vi) = m and A[vi) — {vi^^vi^, . . . ,vi^} be the adjacent set of vi, named 
so that 1 < Ij < I2 < ... < Im- The section {B'{vi,Vi,)) precedes the section 
(5'(?;i, fi,^j)) in s for i = 1,2, ...,m — 1, and there is no other vertex between 
these two sections. 

Corollary 3.3.13 Let {vi,V2, . . . .,Vn) be a vertex sequence of a given n-tree T. 
For any j > I with d{vj) = m. > 2 let A{vj) = {vi,Vj^,Vj^, . . . ,Vj^_^} where i < 



34 

j < ji < J2 < ■■■ < im-i- Then {B'{vj,Vj,)) = ^uj,, Vj, +i, . . . ,Uj,.^.,_i^ for any 
i = 1, 2, . . . , m — 1. In particular, we have that ji = j + I- 

Note that B{vj, v,^_, ) = {vj, Vj^_^ , Vj^_,+u • • • , "j,n-i } is the {vj,vj^_^ )-branch 
vertex set for some j^ > jm-i- 

Corollary 3.3.14 Let (t;i,t;2, . . • ,fn) be a vertex sequence of a given n-tree. If 
i < j with Vj e A{vi) and Vj ^ A{vk) for every k = i + l,i + 2, . . . ,j — 1, then 
Vp ^ A{vk) for every p > j and k = i + l,i-\-2,...,j — 1. 

For any given vertex sequence s = {vi.v^, . . . ,Vn) and any vertex Vj ^ ui, Vi 
belongs to a branch of Vj. We want to give a special name to this branch. 
Definition 3,3.15 Let s = (i'i,f2,- • • ,Un) be a vertex sequence of a given n-tree 
T. For any j > 1 the root branch of Vj in s is the branch of Vj containing Vi. 

Note that there is no root branch for Vi. . . 

Proposition 3.3.16 Let {vi,V2, . ■ ■ ,Vn) E S be the vertex sequence set of a given 
n-tree T. For any I < j < n, if Vj^i A{vj)^ then Vj is an end vertex. 
Proof If Vj^i A{vj) for some 1 < j < n, then Vj has a unique edge with a 
vertex, v,-, with i < j by Proposition 3.3.7. That is, d{vj) = 1. Therefore Vj is an 
end vertex. ± 

Proposition 3.3.17 Let {vi,V2, . . . ,Vn) E S be a vertex sequence set of a given 
n-tree T. For any 1 < j < n there is an integer jm such that 

{vi,V2,...,Vj}[j{Vj^,Vj„+U...,Vn} 

is the vertex set of the root branch of Vj. 

Proof Let I < j < n and d[vj) = m. Then, by Proposition 3.3.10, there exist 
m different vertices, u,-, Ujj, Uj^, • . ■ , Uj„_, such that A{vj) = {wiS^ji, Wj2? • • • '^im-il 
with i < j < ji < J2 < . . . < im-i- From Corollary 3.3.13, we have that 



35 

That is, the union of all the subbranches of Vj except the root branch is a section 
from Vj^ to Uj„_i. Therefore the set of vertices in the root branch is {vi,V2,. ■ ■ ,Vj}U 

Note that, if jm > n, then the root branch is {^1,^2? • • • , ^j}- 
Corollary 3.3.18 Let 5 = (ui, i;2, . . . , u„) € S* be the vertex sequence set of a given 
n-tree T. Let j ^ 1. Then d{vj) — 1, that is, Vj is an end vertex of T, if and only 
if the set of vertices of the root branch of Vj is V{T) = {vi,V2,. ■ ■ ■, u„}- 
Proposition 3.3.19 Let s = {vi,V2, . . ■ ,Vn) be a vertex sequence of a given n- 
tree T. For any vertex Vj with j > I the {vi,Vj)-path in T is a subsequence of 

{vuV2,...,Vj). 

Proof For any vertex Vj with j > I there is a unique vertex Vk^ with kp < j 
such that Vj G A{vkp). For the vertex Vk^ there is another unique vertex Vkj,_i 
with kp^i < kp such that Vk^ G ^(ufcp_i)- Then we will have that Vi is the unique 
adjacent vertex of a previous vertex Vki . Therefore the (ui, Vj)-path is a subsequence 

(ui,Ufc,,...,Ufcp_,,t;ip,Uj} of {vi,V2,...,Vj) . ± 

Proposition 3.3.20 For any two vertex sequences si and S2 in the v-vertex se- 
quence set Sy = {s ^ S\vi = v} the root branch vertex sets of a vertex x ^ Vi — v 
in si and in 62 are same. 

Proof Let s\ = (^1,^2, ■ ■ ■ iVn) and ^2 = (1/1,^2, • ■ • , ■"«) be two different vertex 
sequences of a given tree T with Vi = ui. Let x be an arbitrary vertex in T 
with x / vi. Then there are two integers k and / such that Vk = x — w/. Let 
A{x) = {xi,X2., ■ ■ ■ iXm-iiV}- Since T is a tree, there is a unique (i;i,a:)-path in T. 
Then one of the elements of A{x) is in the (i;i,a;)-path. Without loss of generality, 
let y be in the (ui, x)-path. From the proof of Proposition 3.3.17 we have that 

{u^S,'B'{x,Xp)) = {^^-,'B\vk,Xp)) 

= {vk+uVk+2,- ■ -iVk+r) and 
(U,"LYB'(a:,x,)) ={U';-,'B'{ui,Xp)) 

= {ui+i,Ul+2,---,Ul+r) 



36 



for some r. Therefore we have that 

{vi,V2,...,Vk}U {vk+r-\-U---,Vn} = {?<1 , U2, • • • , "/} U {u/+r+l , • • • , "„}. 

That is, the root branch vertex sets of x in i~i and in S2 are same. ± 
Example 3.3.21 Let T be an 8-tree as shown below. 



.V .w 



r s 

Figure 3-3 



u 



Clearly, si = {q,r,s,t,u,w,v,p) , S2 = {q,p,r,s,w,t,u,v) e Sr ^ {s E 
S\vi = q}. Let 

{vi,V2,...,V8) = {q,r,s,t,u,w,v,p) and (ui,U2, • • • , Ws) = {q,p,r,s,w,t,u,v) . 
Then the root branch vertex set of s is {p,q,r,v}. That is, {p,q,r,v} - {q,r} U 
{u,^} = {vuV2} U {u7,U8} and {p,q,r,v} = {q,p,r} U {v} = {^1,^2,^3} U {ug}- 
Therefore the root branch vertex sets are same but the position might be different. 

On the other hand, d{w) = 1 and the unique adjacent vertex oi w — ve 
is 5 = ^3. Thus s — V3 [s in the root branch of w = Vq. Therefore the root 
branch vertex set of iv = vq is {vi,V2.,V3,Vi,V5,Ve} U {vr^Vg} = {^1,172, ••• ,^8} = 
{q,r,s,t,u,w,v,p}. That is, the root branch vertex set of an end vertex is V{T) 
itself. 

3.4 Degree Sequence 

In this section, we define the degree sequence of a vertex sequence. 
Definition 3.4.1 Let S be the vertex sequence set of an n-tree T. For any ver- 
tex sequence s = {vi,V2,...,Vn) G S, we call Dg = {di,d2, ■ ■ ■ ,dn) the degree se- 
quence of s where di = d{vi) and di = d{vi) — 1 for i > 2. We call the set 
D = {Ds\s G S} the degree sequence set of S. And, for any vertex v £ V, we 



* , . , .• ,-■ f 



•H M5>eH. 



.37 

call Dy = {Ds\s € Sy] C D the v-degree sequence set of Sy. For any section 
{B{vj,Vj,)) = {vj,Vj,,Vj,+i,---,Vj,^i-i) of s, formed by the (uj, v^J-branch vertex 
set B{vj,Vj,), we define Bd{vj,Vj,) = {c([j, ofj,,dj,+i, . . . ,cfj,^i_i} as the (yj,i^j,)- 
branch degree set where cffc = o?(ufc ) — 1 for k — j, j, , j, + 1 , ■ • • , Jt+i — 1 • And we define 
the {vj,VjJ-branch degree section by {Bd{vj,Vj^)) = (^dj,dj-,dj-+i, . . . ,c/j,_^i_i) which 
is denoted by {Bd{vj^)) if there is no confusion. In the same way as in Definition 
3.3.1, we define {Bd'{vj,)) = {Bd'{v^,Vj,)) = (4,(/j.+i, . . . ,o?j.^,_i) . 
Example 3.4.2 Occasionally, it may happen that there are two or more vertex se- 
quences of a given tree with the same degree sequence. In the following example, there 
are several pairs of vertex sequences with the same degree sequences, respectively. 



p r s t 

■■■ ? Figure 3-4 

. 4 • 

Since there are 5 vertices in V(r), there are exactly 5! different sequences of vertices 
of T having length 5 and using each vertex only once. But only 16 of them satisfy 
the condition (*) in Definition 3.3.4. Therefore the vertex sequence set, 5, of the 

given tree, T, consists of the following sequences 

5i = (p,r,q,5,i), S7 = {r,p,q,s,t), sh = {s,r,p,q,t) , 

S2 = {p,r,s,t,q), 58 = (r,jo,5,i,g), sU = {s,r,q,p,t) , 

4 = (g,r,p,5,f), 59 = (r,9,p,s,^), s\s^ {s,t,r,p,q), 

54 = {q,r,s,t,p), s\o = {r,q,s,t,p), s\e = {s,t,r,q,p) , 

55 = {t,s,r,p,q), sn = {r,s,t,p,q), 
se = (i, s, r, q, p) , 5^2 = (r, 5, t, q, p) . 

Then the degree sequences of these vertex sequences are 

D,, =(1,2,0,1,0), D,, = (3,0,0,1,0), Dsi, =(2,2,0,0,0), 

D,; = (1,2,1,0,0), £>,-, = (3,0,1,0,0), D,i, =(2,2,0,0,0), 

D,3 = (1,2,0,1,0), /},-, = (3,0,0,1,0), Dsi, =(2,0,2,0,0), 

!>,-, = (1,2,1,0,0), £>„■„ = (3,0,1,0,0), D,,-, =(2,0,2,0,0), 

Z),-, = (1,1,2,0,0), Dsu =(3,1,0,0,0), 

Z),-, = (1,1,2,0,0), /),f, = (3,1,0,0,0). 



38 



Now we have that 



That is, for some different vertex sequences, the degree sequences might be same. 
And, if the degree sequences are same, then the trees denoted by these degree se- 
quences are isomorphic. 

Remark: The sum of the terms in any degree sequence of a given n-tree is the 
same, namely, n — 1 . It is 4 in the above example, and it is same as the number of 
edges in the tree. See Theorem 3.4.6 below. Since di = d{vi) and </, = d{vi) — 1 for 
i = 2, 3, . . . , n, we have the following proposition. 

Proposition 3.4.3 Let Ds — {di,d2, . ■ . idn) be a degree sequence of a vertex se- 
quence s of an n-tree T. Then < di < n — 1, and < di < n — 1 for f = 2, ...,n. 

Proposition 3.4.4 li dj ^ for any 1 < j < n, then Vj^i is an adjacent vertex 

of Vj. 

Proposition 3.4.5 Let s = {vi,V2, . . . , Vn) be a vertex sequence of an n-tree T and 
Ds = {di.,d2, . . . ,dn) the degree sequence of s. For any j E {1,2, . . . ,n — 1} with 
dj = m > 1, if the set {uj+i, VJ4.2, . . . , u^} is the collection of all the Vj-subbranches 
except the root subbranch, then k > j -\- m. 

Proof Since dj = m = d{vj) — 1, from Proposition 3.3.10, the vertex Vj has m 
subbranches besides the root subbranch. Thus there are at least m endvertices in 
the collection of those subbranches other than the root branch. Therefore at least m 
terms in {dj,dj+i,. ..,dk) are 0. Hence k > j + m. ± 

Theorem 3.4.6 (First Reduced Degree Sum Formula) For any degree sequence 
Ds = {di.,d2,...,dn) of a vertex sequence s ^ S of a given n-tree T we have 

^27=1^' =n- I = \E\ 
and 



39 

Proof di is the degree of a vertex, and the remaining n — 1 terms are each one 
less than the degree of a vertex. By the degree sum formula (Proposition 3.2.7), it is 
true that "^"i-i d{vi) = 2\E\. So 

ELi di ^di+ Y,"=2 di 

= ^(^^i) + EL2 div,) - ^"^2 1 
= {d{vl) + Zl2d{v^))-{n-l} 

= EUd{vi)-in-l) 
^2\E\-{n-l) 
= 2(n-l)-(n-l) 
= n-l = \E\. 

Then we have that 

d.+EUid,--^) = ^1 + Er=2 ^- Er.2 1 
= Er=i di - (n - 1) 

= (n-l)-(n-l) 
= 0. 1 

Corollary 3.4.7 For any degree sequence, Dj = (cfi, c^2, •••,cfn) of a vertex sequence 
s E: S of a given n-tree T, we have 

di + Er=2, d.i^oidi - 1) = Er=2, d.=o 1- 

Proof From the first reduced degree sum formula we have that c^i + E?=2(^'~^) ~ 0- 
Then 

=^i + E?=2K-i) 

= ^1 + Er=2, d,i.oidi - 1) + Er=2, rf.=o('^' - 1) 
= ^1 + Er=2, d,^o('^^- - 1) + Er=2, ci.=o(-i) 

= (/l + Er=2, d,#o(''^' - 1) - E"=2, ci,=0 1- 

Thus we get the result. ± 

Note that di > for any i = 1, 2, . . . , n. So (i, — 1 < if and only if di = 0. 

Corollary 3.4.7 shows that, in a degree sequence D {di,d2,---,dn) , the total 
number of terms is the same as di + E"=2 (di — !)• Therefore there are exactly 
di + Er=2 d.M^di — 1) endvertices in the given tree. Because of this, we have the 
following proposition. 

Proposition 3.4.8 For any degree sequence Ds — {di,d2, ...idn) of a vertex se- 
quence s ^ S of a given n-tree T, we have ■ 



40 

for every 1 < q < n. 

Proof Assume that there is q < n such that di + X1L2(^! — 1) = 0. Since Dg = 
{di,d2,...,dn) is a degree sequence of a vertex sequence s £ S oi the given n-tree 
T, we have that v^+i G A{vp) for some p < q. Thus at least one of the endvertices 
counted by Vp is one of u,+i, v,+2, • ■ • i '^n- That is, in the section {di,d2, ■ ■ ■ ,dg) , 
we have at least one less terms than di + X^^_2 d,=,to(^' "" ^)i ^^^^ ^^' 

^i + EU..^oK-i)-EL2,..=oi>i- 

Then 

=^i + EL2K-i) 
= di + EU .i^M^^ - 1) + EL2, ..=o('^^- - 1) 
= ^i + EU..^oW-i) + EU..=o(-i) 
= ^i + EU..^o(^»-i)-EU<i.=oi 
> 1- 

This is a contradiction. Therefore we have di + E!=2(^« "" 1) 7^ ^"^^ every 1 < q" < 
n. 1 

Theorem 3.4.9 (Second Reduced Degree Sum Formula) Let T — (V, E) 

be an n-tree. Let Ds = {di,d2, ...,dn) be the degree sequence of a vertex sequence 
s E S of the given n-tree T. For any jk > 1, let B'{vji^) = {vj^,Vj^^i, ...,Vj^^^-l} 
be a {vj,Vj^)-subbranch vertex set. Then we have 

^;.+Es:;;(^«-i) = o 

and 

for every jk < q < jk+i- 

Proof Let E{B\vj,)) = {{u,v] G E{T)\u,v E 5'(u,J}. Then 

rKJ = (5>,j,£;(5'K)))cr 

is also a tree, and {B'{vjJ) = (uj^, u^^^.!, . . . ,t;j^^,_i) is a vertex sequence of the 
tree T{vj^). Note that d{vj^) = dj^ + l in T. Since Vj ^ B'{vj^), the edge {vj.Vj^} 
is not in the edge set E{B'{vj^)). Thus we have that d{vj^) = dj^ in the subtree 



41 

T{vj^). Then the result comes from the first reduced degree sum formula (Theorem 
3.4.6) and Proposition 3.4.8. 1 

Corollary 3.4.10 Let s = (wi,U2, . . . , Un) be a vertex sequence of an n-tree T and 
Ds = {di,d2y. . .,dn) the degree sequence of s. For any dj > 0, if the subsequence 
{vj,Vj+i,. . . ,Vp) is the collection of all the Vj-branches except the root subbranch of 



Uj, then 



and 



^. + EL+i(^«-i) = o 



for every j < q < p- 

Proof For j = 1, they are true by the first reduced degree sum formula (Theorem 

3.4.6) and Proposition 3.4.8. Let j > 1 and Vj 6 A{vt) for some t < j. 

(i) If dj = 0, then d{vj) = 1, that is, Vj is an end vertex. Since j > 1, Vj ^ V\. 
Thus the root branch is the whole tree by Corollary 3.3.18. Therefore {vf) is the 
collection of all the Uj-branches except the root subbranch and dj + Y7i=j+i{^i ~^) — 
d, =0. 

(ii) If dj > 0, then the subsequence {vj, Uj+i, . . . ,Vp) which is the collection of all 
the f j-branches except the root subbranch, is the {vt, z;j)-subbranch, since Vj € A(vt). 
By the previous theorem, we get dj + X^^=j4.i(<^i — 1) = 0. Thus the collection of all 
the Uj-branches except the root subbranch of Vj is the (u^, t;j)-subbranch. Therefore, 
by the second reduced degree sum formula, we get dj + X1Lj+i(^' ~ 1) t^ ^^^ every 
j < q < p. ± 

Not all of the nonnegative integer sequences with n entries can be a vertex 
sequence of an n-tree. There is a condition to being a degree sequence of an n-tree. 
Definition 3.4.11 Let D = ((/i,(/2, . . . ,</„) be a nonnegative integer sequence. 
We say that D satisfies the degree sequence condition^ briefly DSC, if and only if it 
satisfies all of the following: 

4 

■■'.'•:■: * •„ . i"- ;> V a 



42 



(a) di >0. ' 

(c) For any j < n with clj - m > 0, there are exactly m + 1 integers, j < ji - 
j + 1 <J2< ■■■<jm< Jm+i(= n + 1 if i = 1), such that 

^..+E-i^:;;(^-l)= for A; = 1,2,..., m. 

(d) For any jk with dj^ = / > 0, there are exactly / + 1 integers, jk < jki - 

jk + \ < jk, < ...< jk, < jk^,+^^ = jk+i such that 

Theorem 3.4.12 Let D = {di,d2.,. . .^dn) be a nonnegative integer sequence. Then 

D is a degree sequence of a vertex sequence of an n-tree if and only if D satisfies 

DSC. 

Proof [=>] This follows from Proposition 3.4.3, Theorem 3.4.6 and Theorem 3.4.9. 

[<=] Let V = {vi,V2,. ■ .^Vn} be a set of n different vertices. Let D = 
{di,d2,. . ■ ,dn) be a nonnegative integer sequence satisfying the above conditions. 
Since di > and di > for any i = 2, 3, . . . , n, we can assign the degree of each 
vertex vi G V by d{vi) = di and d{vi) = di + 1 for ? = 2,3, . . . ,n. Let j <n and 
dj = m > 0. From (c), there are exactly m + 1 integers, j < ji < J2 < ■ ■ ■ < jm < 
jm+u such that ji = j + l, and dj^ + Eiljl+i(^i - 1) = for k = 1,2, ...,m. Now 
we assign an edge between Vj and Uj^ for A; = 1,2, . . . ,m. That is, Vj,^ G A{vj) 
for i = 1, 2, ...,m. 

(i) If dji^ = / > 0, we assign an edge between Vj^ and Vj,^ for p = 1, 2, . . . , / 
by (d). We do a similar procedure for each vertex, Vj, assigned to dj > 0. Therefore 
Vj^ G A{vj) and Uj^ G A.{vji^) for /c = 1, 2, . . . , m, j = 1, 2, . . . , /. 

(ii) If dj, = 0, then we do not assign any new edge for the vertex Vj,. But it is 
already joined to the vertex Vj by an edge. 

Let J = (ui, U2, . . . , Vn) ■ Then all the vertices in s are connected. Since each vertex 
Vi is assigned di new edges and Yll-i di = n — 1 from (b), we have n vertices and 



43 

n - 1 edges. Then the set of all the edges assigned above, together with the vertex 
set V, forms an n-tree by Proposition 3.2.6. -L 

Remark: The proof of Theorem 3.4.12 shows how to construct a tree that corre- 
spond to the given degree sequence satisfying DSC. 

Example 3.4.13 Let £> = (3,2, 3, 1, 0, 0,0, 1,0,2, 0,0,0) be a nonnegative integer 
sequence having 13 entries. Let V = {ui, U2, • • • , v„} be a set of n different vertices. 







^9 


s 






.U12 


► 1^13 


Vs 


V7 






vw 


^1 


V2 


V3 


V4 


V5 


• 













vn 



ve 



Figure 3-5 



(a) Clearly, X^-^j di = 12 and di = 3 > 0. So we expect a 13-tree. 

(b) Since d{vi) = 3, there are 4 different integers, I<li=2<l2 = 10<l3 = 
13 < I4 = 14, such that d2 + Etsl^' -1) = 2 + (2 + 0-1-1-1 + 0-1) = 
0, dio + Y^lliiidi — l) = 2 + ( — 1 — 1) = 0, and 0^13 = 0. We assign edges between 
Vi and each of ^2,^101^13. 

(c) (i) Since V2 = 2, there 3 different integers, 2 < 3 < 8 < 10, such that c?3 + 
J2LM - 1) = 3 + (0 - 1 - 1 - 1) = 0, and 4 + (dg - 1) = 1 - 1 = 0. We assign 
edges between V2 and each of V3 and vg. 

(ii) Since Vw = 2, there are 3 different integers, 10 < 11 < 12 < 13, such that 
dii = and di2 = 0. We assign edges between fio and each of vn and fi2- 

(iii) Since U13 = 0, we do not assign any new edge for ^13. But the vertex i;i3 
is connected to vi by an edge. 



44 

In a similar way, we get {v3,V4},{v3,ve},{v3,V7},{vs,V9}, and {v4,V5}. Let E be 
the collection of all the edges above, that is, 

E = {{^^1, t^2}, {Ul, Uio}, {Vl, U13}, {"2, V3}, {U2, Vs}, {Uio, ^^u}, 
{Vl0,Vi2},{v3,V4},{v3,Ve},{v3,V7},{Vs,Vs},{v4,Vn}}. 

Since the edge set E contains 12 elements, the set T = {V, E} is a 13-tree. 

3.5 Perfect Sequence and Main Theorem 

In the previous section, we showed that, for a given n-tree T, there exist many 
vertex sequences depending on the starting vertex and choice among the adjacent 
vertices for each successive vertex. Therefore the degree sequence set D for the 
given tree T contains many different degree sequences which denote the same tree 
T. We need a way to choose one degree sequence representing the tree T. First of 
all we want to define an order on the set of all finite, nonnegative, integer sequences. 
Definition 3.5.1 For any two finite nonnegative integer sequences D = {pi,p2i ■■■■,Pk) 
and E = {qi-,q2, ■■■,qi) , D < E \i and only if either there is m < min{A;,/} such 
that pm < q-m and p,- = gi for all i = 1, 2, . . . , m — 1, or k < I and pi = qi for all 
i = 1, 2, . . . , A;. We write D < E \{ D < E ox D = E. 

Proposition 3.5.2 Let D be the set of all degree sequences of an n-tree. The degree 
sequence set, (jD, <), is a totally ordered finite set. 

Proof For any two different degree sequences the order defined above is well defined. 
Since each term di of a degree sequence is nonnegative and less than n and the 
length of each degree sequence is n, the degree sequence set D is a, finite set. Thus 
{D., <) is a totally ordered finite set. ± 

Definition 3.5.3 For a given n-tree T, let S be the vertex sequence set of T and 
D the degree sequence set of T. Then the maximum degree sequence in D is called 
the perfect sequence of the given tree T, and it is denoted by pf[T). For the perfect 
sequence, pf{T), of a given tree, T, there is a vertex sequence s = {vi,V2.,...,Vn) G 



45 

S such that the degree sequence of s is pf{T). We call s a perfect vertex sequence 
of the tree and Vi a perfect vertex of the tree. 

In the Example 3.4.2, the perfect sequence is (3, 1,0,0,0) and there are two 
different perfect vertex sequences, ^n = {r,s,t,p,q) and Su = {fiS,t,q,p) for it. 
But the trees represented by 5ii and 512 are isomorphic. 

For any given tree the perfect sequence is unique by Proposition 3.5.2. But 
there may exist several different perfect vertex sequences. If the given tree is a 
labeled tree, then these perfect vertex sequences denote different labeled trees. But 
these labeled trees are isomorphic to each other; that is, there is a unique unlabeled 
tree. Therefore, for a given perfect sequence, there exists a unique unlabeled tree. 
Theorem 3.5.4 Let dg be the perfect sequence of a tree T. If T' is any other tree 
whose perfect sequence is also dg, then T' is isomorphic to T. 

Proof If T has more than one vertex sequence with the same degree sequence, then 
these vertex sequences all produce the isomorphic trees, by using the construction in 
the proof of Theorem 3.4.12. J. 

Because of this theorem, we have our main theorem below. 

Theorem 3.5.5 (Tree Classification Theorem) For any positive integer n, let 
T[n) he the set of unlabeled n-trees and V{n) the set of perfect sequences of n-trees. 
Then there is a one-to-one correspondence between T{n) and V{n). 

3.6 Obtaining Perfect Sequences 

By Theorem 3.5.5, if we can construct the set of perfect sequences of n-trees, 
V{n)^ without being given any tree shape, then we can classify all the n-trees by this 
set. And, in the same way as in Example 3.4.13, we can get the different tree shapes 
from the elements of V{n). 

Proposition 3.6.1 For the perfect vertex Vi of a perfect vertex sequence s = 
(f 1, V2, ..., Vn) , we have d{vi) > d{vi) for i = 2, 3, . . . , n. 



46 

Proof If there is some k G {2,3,...,n} such that d{vk) > d{vi), then D^ = 
{d{vi), . . .) < Ds' - {d{vk), . . .) for any vertex sequence s' - {vk, . . .) . This contra- 
dicts the maximality of Dg. 1. 

Proposition 3.6.2 // Ds = {di,d2, ...,dn) is the perfect sequence of a given n-tree 
T, then n — 1 > di > di > dn — for any i = 2,3, ..., n — 1. 

Proof Since T is an n-tree and Ds is the perfect sequence, we have n — l>di. For 
any vertex u G V{T) we have d{vi) > d{u) by Proposition 3.6.1. Since di = d{vi) 
and di = d{vi) — 1 for every 1 < i < n, we have di > di for 1 < i < n. Since dn 
must denote one of the end vertices, each of which has degree 1, we have dn = 0. 
Therefore we have di > c?„ = for every 1 < i < n — I. 1. 

Definition 3.6.3 Let D = {di,d2, ...,dn) be a degree sequence. Then we say that 
D satisfies the ordered subbranch condition, denoted OSbC, if and only if D satisfies 
the following condition for all j > 1 : 

If d{v,) = m -f- 1 > 2, and B'{vjJ, 5>,J, ..., B'{vjJ with j < ji < j2 < 
... < j„i are the subbranches of the vertex Vj other than the root subbranch, then 
{Bd'{vj^)) > (Bd'ivj^^^)) for every A; = 1, 2, . . . ,m - 1. 

Recall that {Bd'{vj-)) is a section of the degree sequence D. (See Definition 
3.3.3 and 3.4.1.) 

Remark : If j = 1, then there is no root branch of Vi; instead, there is one more 
subbranch, Bd'{vj^^^), such that j„ < jm+i and {B'{vj^)) > {Bd'{vj^_^J) . 
Theorem 3.6.4 Let D — {di,d2, . . . ,dn) be a nonnegative integer sequence. If D 
is the perfect sequence of an n-tree, then it satisfies the DSC and the OSbC. 
Proof It is clear from Theorem 3.4.12 and the maximality of D. ± 
Proposition 3.6.5 Let T be a tree and v a vertex with the largest degree in T. 
Then there is exactly one degree sequence Dy for T starting at v and satisfying 
both DSC and the OSbC. ' \/::' ■' : v ..; 



rV.. 



47 

By the above proposition, the converse of Theorem 3.6.4 is not true. The 
following example is a counterexample. 

Example 3.6.6 Let A = {dud2, . . . ,du) = (3,2,2,1,0,0,2,0,0,1,0,0). Then 
Sill ^» = 11 and di = 3 > 0. And the sequence A can be separated into 4 
sections like (3), (2,2,1,0,0,2,0,0), (1,0), (0) . The second section can be sep- 
arated into 3 sections, (2), (2,1,0,0), (2,0,0), and the second and third sec- 
tion of these can be separated by (2), (1,0), (0) and (2), (0), (0), respec- 
tively. All of these subsections satisfy the second and third conditions of DSC. 
Thus the sequence A satisfies the DSC. That is, the sequence A is a degree se- 
quence of a vertex sequence {vi, ^2, . . . , f 12) of a 12-tree by Theorem 3.4.12. On the 
other hand, the sequence A satisfies the OSbC, since we have (2,2, 1,0,0,2,0,0) > 
(1,0) > (0) . But A is not the perfect sequence of the 12-tree. In fact, we rearrange 
the sequence A to get B = {dr + l,d2^di — l,dio,du,di2.,d3,d4,d5,de,d8.idQ) = 
(3,2,2,1,0,0,2,1,0,0,0,0). Note that d{vi) = di and d{v7) = d7 + l. Clearly the 
sequence B also satisfies the DSC and the OSbC. So B is also a degree sequence 
of another vertex sequence (^7, ^2, ^i, ^^10,^11? ^12) ^^3, ^4, ^5, V6,^^8, ^9) of the 12-tree. 
That is, A and B are degree sequences of the same 12-tree (see Figure 3-6). And 
we have 

B = (3, 2, 2, 1, 0, 0, 2, 1, 0, 0, 0, 0) > (3, 2, 2, 1, 0, 0, 2, 0, 0, 1, 0, 0) = A. 
Thus A is not the perfect sequence. Furthermore A cannot be the perfect sequence 
of any tree, because A and B denote isomorphic trees, and B > A. 

Vu t;io Vi t;i2 



V2 




Vr, V4 Vs Vq 

Figure 3-6 



48 

In this example we have that d{vi) = 3 = cfff?) which is the largest degree 
in the tree. That is, the perfect sequence must start with the largest degree. We will 
see in Example 3.6.8 that the degree sequence B is the perfect sequence of this tree. 

Note that (1,0) is the only possible degree sequence when c?i = 1. Therefore 
we assume di > I from now on. 

Now we show how to construct alternate degree sequences from A, similar 
to B. Assume that we have a nonnegative integer sequence A = {di,d2, ■ ■ ■ ,dn) 
satisfying the DSC and the OSbC. If there is 1 < i < n such that di < di, then 
A cannot be the perfect sequence of any tree by Proposition 3.6.2. So we assume 
that di > di for i = 2,3, ...,n, and there is at least one integer 1 < j < n such 
that dj = di — I. That is, there is an n-tree T = {V, E) such that A is a degree 
sequence of a vertex sequence s = (ui,U2, . . . , ?;„) of T, and T has at least two 
vertices of maximum degree di. Clearly, dj > 0. Thus Vj is not an end vertex in 
T. By Corollary 3.3.18, the set of the vertices of the root branch of Vj is not the 
set of vertices in A itself. So, from Proposition 3.3.17 there is j < m < n such 
that RB{vj) = {vi,V2.,. . . iVj} {J {vm+i,Vm+2, ■ ■ ■ i^n} is the set of the vertices of 
the root branch of Vj. Clearly, (uj+i,Uj+2, ■ • • , fm) is the section containing all of 
the subbranches of Vj except the root branch. Therefore, if dj = p, then there are 
p subsections of A Hke {Bd'{vj^)) > {Bd'{vj^)) > ... > (Bd'{vj^)) with j < ji < 
J2 < ■ ■ ■ < jp < m + 1, since A satisfies OSbC. On the other hand, let E{RB'{vj)) = 
{{u,v] e E{T)\u,v G RB'{vj)} be the set of edges in the root subbranchoi Vj. Then 
r = {RB\vj),E{RB'{vj))} is a subtree of T. Let S{T') be the vertex sequence 
set of T'. By Proposition 3.3.7, there is a unique integer 1 < A; < j such that 
Vk G A{vj). Clearly, Vk G RB'{vj). Let ^^^(r') be the t;fc-vertex sequence set of 
S{T'), in which the first term of each vertex sequence is Vk. Let Dy^{T') be the 
Vk-degree sequence set of Sy^{T') (see Definition 3.4.1). Since Dy^{T') is a finite 
set, there is a maximum sequence in Dy^{T'). We denote the maximum sequence in 



49 

Dy^{T') by mdR{vk). Note that di must be changed to di - \ in mdR{vk), since 
it is not going to be used for the first term anymore in the new degree sequence. 
Now we have that either mdR{vk) > {Bd'{vj^)) , or there is an integer I < q < V 
such that {Bd'{vj^)) > mdR{vk) > {Bd'{v^^^^)) . Note that mdR{vk) may be the 
smallest section, then Vj^_^^ would not exist. 

We rearrange the given degree sequence A to a new sequence in which dj + 1 
is the first term and the subbranch degree sequences of Uj, 

mdR{vk), {Bd'{v,,)), (Bd'iv,,)), ..., {Bd'{vj^)) , 
are listed in descending order. Denote this new degree sequence by M^ . 

Since the subbranch degree sequences of Vj are listed in descending order in 
M^, the new degree sequence M^ satisfies the OSbC. Since M^ is a rearrangement 
of A with di = d{vj) = t/j + 1 > 0, di = d{vi) - I = di - 1 for some i > 1, and 
A satisfies the DSC, the new degree sequence M^ satisfies the conditions (a) and 
(b) of the definition of the DSC. Since mdR{vk) is the perfect sequence of T', it 
satisfies the conditions (c) and (d) of the definition of the DSC. Clearly, each section, 
{Bd'{vj,)) , satisfies the conditions (c) and (d) of the definition of the DSC. Therefore 
the new degree sequence M^ satisfies the DSC. Thus the new degree sequence M^. 
satisfies both the DSC and the OSbC. 

For the given nonnegative integer sequence A = (c/i, c?2, . . . ,c?n) > the set 
{M^\d{vj) = d{vi)} is a non-empty finite set, since A € {M^\d{vj) = d{vi)}. 
Therefore there is a maximum element in this set. Let Pa = max{M^\d{vj) = d{vi)}. 
Now A determines a unique tree T. Suppose B is another vertex sequence for T 
satisfying the DSC and the OSbC. Then {M^Jd{vg) = d{vi)} = {M„^|c/(uj) = d{vi)}, 
where Vq is an analogue of Vj, by Proposition 3.6.5. Therefore Pa is the perfect 
sequence fbr T. ' '. : * ^ / ^ ''A in 

By the above explanation together with Proposition 3.6.2 and Theorem 3.4.12, 
we have the following theorem. v '• "i -^ . ' ' t .<' 



50 



Theorem 3.6.7 Let A = {di,d2, . . . ., dn) be a nonnegative integer sequence satisfy- 
ing the DSC and the OSbC with di > d, for i = 2, 3, . . . , n. Then A = Pa if and 
only if A is the perfect sequence of an n-tree. 

In the following example, we show the degree sequence B in Example 3.6.6 
is the perfect sequence of the tree. 

Example 3.6.8 In Example 3.6.6, 

A=(di,4,...,^i2) = (3,2,2,1,0,0,2,0,0,1,0,0) 
satisfies the DSC and the OSbC and d2 = d^, = dy — di — l. That is, d{v2) = d[v2,) — 
d{v7) = d{vi). Thus max{M^|_;' = 2,3,7} is the perfect sequence of the tree. For 
V7 we have that RB{v-r) = {t;i,U2, • • • , ^7} U {^10,^11,^12} and {Bd'{vs)) = (0) = 
{Bd'{vg)). Thus V = {RB'{v7),E{RB'{v7)} is the subtree produced by the root 
subbranch of vj. (See Figure 3-7.) 
Since vj G ^(172), we get the ^7- vertex sequence set 

Sy,{T') = { {v2,Vi,Vio,Vu,Vi2,V3,V4,V5,Ve) , 

(t;2, ui, U12, Uio, uii, U3, ^4, U5, ve) , 
{v2, ui, U12, uio, Vn,V3, Ve, V4, V5) , 

{v2,V3,V4,V5,Ve,Vi,Vio,Vu,Vi2) , 
(U2, ^^3, V4, U5, ^6, Ul, ^^12, ^^10, f u) , 
(1^2, t^3, ?^6, W4, V5, ^^1, t^lO, ?^11, ^^12) , 
{v2,V3,Ve,V4,V5,Vi,Vi2,Vw,Vu) }■ 

Then the Vr-degree sequence set of Sy^{T') is 

Dy,ir) ={ (2,2,1 
(2,2,1 
(2,2,0 
(2,2,0 
(2,2,1 
(2,2,1 
(2,2,0 
(2,2,0 
= { (2,2,1 
(2,2,1 
(2,2,0 
(2,2,0 



,0,0,2,1 


,0,0), 


,0,0,2,0 


,1,0), 


,1,0,2,1 


0,0), 


,1,0,2,0 


1,0), 


,0,0,2,1 


0,0), 


,0,0,2,0 


1,0), 


,1,0,2,1 


0,0), 


,1,0,2,0 


1,0)} 


,0,0,2,1 


0,0), 


,0,0,2,0 


1,0), 


,1,0,2,1 


0,0), 


,1,0,2,0 


1,0)} 



51 



Therefore we have the maximum sequence mdR{v7) in Dy^{T') as mdR{v'j) — 
(2,2,1,0,0,2,1,0,0). Since mdR{vr) = (2,2,1,0,0,2,1,0,0) > (0) = {Bd'{vs)) = 
{Bd'{v<,)), we have M^ = (3, 2, 2, 1,0,0, 2, 1, 0,0,0,0) . 
In the same way, we get 

M^ =(3,2,1,0,0,2,1,0,0,2,0,0) 
M4 =(3,2,2,1,0,0,2,0,0,1,0,0). 

Therefore niax{MyJj = 2,3,7} = My^. Since 

M4 =(3,2,2,1,0,0,2,1,0,0,0,0) 
> (3,2,2,1,0,0,2,0,0,1,0,0) 
= A, 

M^, which is B in the Example 3.6.6, is the perfect sequence of the tree. 



vn t?io 



Vi 



1^12 



V2 



t>5 ^4 ^^3 ^^6 

Figure 3-7 



By the Tree Classification Theorem (Theorem 3.5.5) and the previous example, 
we have the following important corollary. 

Corollary 3.6.9 Let A = {d\^d2^. . . ^dn) be a nonnegative integer sequence satis- 
fying the DSC and the OSbC. If di — I > d^ for every i = 2, 3, . . . , n, then A is the 
perfect sequence for an n-tree. 

We will see in the following example how we construct a tree shape from a 
given maximal degree sequence. 

Example 3.6.10 Let D = ((/i,(/2, ..., c/io) = (3,2, 1, 2,0, 0, 1, 0,0,0) be a maximal 
degree sequence. Then we expect a 10-tree, T. Let i = (ui, V2, . . . , ^;io) be the vertex 
sequence having D as the degree sequence. Then d{vi) = di = 3, so the vertex Vi 



52 

has 3 edges. (See Figure 3-8.) Though there is no specific order for these edges, we 
label them as ei, 62, 63 for the convenience of explanation. 



62 



63 vi ei 
Figure 3-8 

From the definition of vertex sequence (Definition 3.3.4) V2 is one of the 
elements of the adjacent set of vi, A{vi). Without loss of generality, let ei = 
{^1,^2}. Then ^2 has 2 'new' edges, 64 and 65, since c?2 = 2. Let 64 = {f2,y3}- 
By the same reasoning, V3 has 1 'new' edge, named cq. So cq = {t>3, V4}. Since 
(^4 = 2, V4 has 2 'new' edges, named 67 and es- (See Figure 3-9.) 



€2 



e» 



68 



63 Vi Ci U2 64 ^3 ^6 1^4 67 

Figure 3-9 

Since c/5 = and (/e = 0, neither V5 nor Ue has a 'new' edge; that is, v^ 
and ve are end vertices. On the other hand, v^ and ve are the adjacent vertices of 
V4, since ((4 = 2. Thus vj is an adjacent vertex of one of {vi,V2iV3}. Since c?3 = 1 
and V4 is the adjacent vertex of V3, V3 is not an adjacent vertex of vj. Since 
(^2 = 2 and we have only one adjacent vertex of U2, namely U3, we add an adjacent 
vertex, vr. (See Figure .3-10.) 



t?7 



V6 



62 



65 



68 



^3 Di ei ^2 64 U3 ^6 V4 er y^ 
Figure 3-10 



53 

Since dr = 1, vj has 1 'new' edge which connects with vs- Since ds = 0, 
there is no 'new' edge from vg. Since we covered up to d2, the remaining two vertices, 
vq and uio, are adjacent vertices of vi which has two 'unused' edges, 62 and 63. 
Let 62 = {vi,vq}, and 63 = {ui,i^io}- Since we are thinking about an unlabeled tree 
and we put the edge names for our convenience, there are no specific names for the 
vertices and edges. Thus we get the following 10-tree. (See Figure 3-11.) 



M 



w^ 



i( 



(vs) 



{V7) 



(ve) 



(wio) (vi) {V2) (vs) {V4) 
\0''i'';*^'' Figure 3-11 



(^5) 



3.7 Extended Partitions and the Algorithm 

In Definition 3.5.3 and the following explanation, it was shown that any tree 
can be represented by a unique perfect sequence. So, in this section, we develop an 
algorithm to produce all the perfect sequences for the n-trees for any positive integer 
n. From these perfect sequences, we get the shape of each n-tree as shown in the 
previous example, as well as the total number of n-trees. 

From Definition 3.4.1 and the First Reduced Degree Sum Formula (Theorem 
3.4.6), we see that a degree sequence for an (n -|- l)-tree always has n-\-l nonnegative 
integers as entries and these integers always add up to n which is the number of 
the edges of the given (n + l)-tree. Thus, our first step in listing all possible degree 
sequences is to form ordered partitions of the integer n as sums of smaller positive 
integers. 



54 

Definition 3.7.1 An ordered partition of the positive integer n is a sequence of 

positive integers, (pi,P2, • • • ,Pm) , such that YllLi Pi = "• 
Note that I < m < n in the definition above. 

Definition 3.7.2 An extended partition of an ordered partition {pi,p2., . . . ,Pm) of 

the positive integer n is a sequence of n + 1 nonnegative integers, (c?i, (/2, • • • , dn+i) , 

such that 
{i)di=pi, X^"j"/ (fi = n, and . ; " 

(ii) there is a subsequence {dj^ ,dj^,..., dj^) such that dj^ = pk for A; = 1, . . . , m. 

Note that any entry di in the extended partition must be unless it is a 
member of the ordered partition. It is important that different extended partitions 
are produced not only by the different ordered partitions but can also be produced 
by the same ordered partition. 

For example, let ((ii,d2, . . . ,c?„+i) and (c?i, 6^2, . . . ,o('„^i) be two extended 
partitions of an ordered partition (pi,p2, • • • ,Pm) , and let {dj^,dj^, . . . ,dj^) and 
(rfjprfj^, • • • ,of(^) be subsequences, respectively, such that dj^ — di = pi = d[ and 
dj^ = Pk = d[^ for A; = 2, 3, . . . , m. Assume that ji ^ ti for at least one i. Then 
there are sections of zeros with different lengths between di,^ ,, and cf,- , and d'. 
and d'f^, respectively. So the extended partitions are different. Thus the order is 
very important in an extended partition. 

Also note that the length of the extended partition of n must be n + 1. So, 
for any given ordered partition, {pi,p2, ■ ■ ■,Pm) , we need to add n-m + l zeros to 
make an extended partition. 

Proposition 3.7.3 Let (c?i, c?2, • • ■ , c^n+i) be an extended partition of an ordered 
partition P = {dj^,dj^, . . . ,dj^) of the integer n. Then this extended partition sat- 
isfies the First Reduced Degree Sum Formula (Theorem 3.4.6). 

■ f.' .: 'r '^T '■'...■'.■'- t^ y '^' '^--r 

' ,' , i ■■ \ i % ' ■ . i J 



55 

Proof From the given extended partition ((/i, (^2, ■ ■ • , dn+i) of an ordered partition 
{dj^ , c^j2, . . . , dj^) of the integer n, we have that Xl"=i di = YlT=i ^h - " ^"^ 
^1 + ES (^»- - 1) = ^1 + Er=2(^.. - 1) + ES! d.0F(^^- - 1) since d, + 

= d,, + Er=2(^.. - 1) + EK ..^p(^. - 1) 
= Er=i ^.. + Er=2(-i) + ES, ..^p(-i) 

= n + (m - 1)(-1) + (n - m + 1)(-1), 
:=n — m + 1— n + m— 1 = 0. ± 

Even though we have a very large number of extended partitions of n, some of 
them can not be a maximal degree sequence for an (n + l)-tree. So we first eliminate 
some ordered partitions that could not possibly result in maximal degree sequences. 
To do so, we need to check some properties of perfect sequences. 

Proposition 3.7.4 Let Ds = {di,d2,. . . idn+i) be the perfect sequence of a given 
(n + l)-tree T. If di ^ and di^i = 0, then = di^i = di^2 = ••• = <^»+di- 
Proof Since di^Q, the vertex Vi has di 'new' edges; that is, there are di adjacent 
vertices of u, and they are labeled by di consecutive integers after i. Since Dg is 
a perfect sequence, it satisfies the OSbC. That is, the vertex Uj+i is a vertex of the 
largest degree among the adjacent vertices of Vi. But di^i = 0. Therefore we have 
dj = for j = f + 2, i + 3, . . . , i + di. ± 

This proposition gives us a method to make an extended partition from an 
ordered partition by adding zeros. That is, we know certain extended partitions 
cannot be perfect sequences just by checking this property. 

Proposition 3.7.5 Let Dg — {di,d2, . . . ,dn+i) be the perfect sequence of a given 
(n + l)-tree T. If n > 2, then di > 2. 

Proof If di = 1, then di = for every i = 2,3, . . . ,n + 1 by Proposition 3.6.2. 
Since n > 2, there are at least 3 vertices in T. Thus we have that <^i + E"=2H^«~l) = 
1 + E"=2 ("~1) ^ 1 + (~1 — 1) = — 1 / 0. This is a contradiction to the First Reduced 
Degree Sum Formula. Therefore di > 2. ± 



56 

According to the above proposition, the only trees whose perfect sequences 
start with or 1 are the tree with zero edge and the tree with one edge. The only 
degree sequence representation of a tree with zero edge is (0) , and the only degree 
sequence representation of a tree with one edge is (1,0). These are easy enough to 
visualize and count, so for the algorithm we work on the assumption that we are 
listing trees with at least two edges. Then the first term of the perfect sequence will 
be at least 2. 

The following proposition shows that we have an arc shape tree if the first 
term of the perfect sequence is 2. 

Proposition 3.7.6 If Ds = ((/i,(/2, • • • i^^n+i) is the perfect sequence of an {n-\-l)-tree 
T and di — 2, then di = 1 for i = 2, 3, . . . , n — 1 and dn = dn+i = 0. 

Proof By Proposition 3.6.2 we have that di € {0, 1} for any i = 2,3, . . . ,n + 1, 
since di = 2. Then the possible highest degree in T is degree 2. So T is just a 
linear tree with n edges. That is, there are exactly two end vertices which cannot be 
^1. Therefore there are exactly two zeros in the sequence. Write a degree sequence 
for T, in the order of the vertices in the following figure. 



^'n+l Vi V2 V3 Vn-1 Vn 

Figure 3-12 

That is, start at a vertex adjacent to an end vertex and move in the longer 
direction first. Clearly the degree sequence resulting from this method contains 
the two zeros for Vn and Vn+i- Then we will get a degree sequence of the form 
D — (2, 1, 1, . . . , 1, 0, 0) . For the same tree, the numbers in a degree sequence cannot 
change, but only the order in which they occur can change by changing the position 
of zeros. And, clearly, the new ordered sequence < D. So the sequence D must be 
the perfect sequence of T. That Is, Ds = D. ± 



57 

Most of the extended partitions of n start with a 1 or a 2. Since the last two 
propositions classify trees whose degree sequences start with these values, we do not 
need to consider ordered partitions that start with 1 or 2. 

Proposition 3.7.6 shows that for any given number n of edges there is only one 
tree with n edges whose perfect sequence starts with a 2. In particular, it is a linear 
tree with n edges, since d^ = I for i = 2, 3, . . . , 7Z — 1. We add this sequence at the 
end of the algorithm. 

By Propostion 3.6.2, we do not need the ordered partitions in which the largest 
summand appears more than once or is not the first term in the ordered partition. 

If an ordered partition has either one or two entries only, then we can produce 
only one extended partition for each case. See the following Proposition 3.7.7 and 
Corollary 3.7.8. 

Proposition 3.7.7 Let Dg = {di,d2, ■ . ■ ,dn+i) be the perfect sequence of an {n + 1) - 
tree T with c?2 = 0. Then di = n and di = for all i > 1. 

Proof: Let J be a vertex sequence yielding a perfect sequence Dg of an (n + 1)- 
tree T. Since Dg is a perfect sequence and — d2 = d{v2) — l, all of the vertices in 
the tree other than Vi have degree 1, so all the terms in Dg other than di must be 
zero. By the First Reduced Degree Sum Formula (Theorem 3.4.6), we have di = n. L 
Corollary 3.7.8 If an ordered partition P = (pi,p2) "/ n has only two entries, 
then the produced extended partition, (c/i, (i2, . . . , c?n+i) , from P is such that di = 
Pi 5 <^2 = P2 and di = for i = 3, 4, . . . , n + 1. 

We demonstrated several necessary conditions which apply to a perfect se- 
quence of a tree. Unfortunately, while these conditions are sufficient in almost all 
cases, there are certain sequences which, although they satisfy all the conditions, are 
not perfect sequences of the trees they represent. The problems usually arise when 
the tree has two or more vertices of the largest degree. We saw a counterexample in 
Example 3.6.6. 



58 

Note that in the Example 3.6.6 the two degree sequences A and B have the 
same ordered partition, P = (3,2,2,1,2,1). That is, our algorithm produces the 
degree sequence B as one of the extended partitions of the ordered partition P. 
Therefore all we need to do is just drop the degree sequence A from the result of 
our algorithm. 

Each step described so far has involved checking each member of a list of 
possible degree sequences and removing those which could not be the perfect sequence 
of a tree. The last step is no exception. Given a degree sequence, we check if there is 
more than one vertex of maximal degree. If there are more than one (in Example 3.6.6, 
both vertices vi and vj — u\ have the same degree, 3), we write degree sequences 
for the tree starting at each such vertex. If the largest of these with respect to 
the ordering < is the sequence we are checking, then it is a perfect sequence. If 
some other vertex gives a larger degree sequence, it is false that the sequence we are 
checking is a perfect sequence. This is a surefire approach in that, given a degree 
sequence, it checks for a perfect sequence by considering every possible alternative 
for the maximum and seeing if the sequence in hand is the largest. 



CHAPTER 4 
TREES AS INVARIANTS FOR BRAIN TUMOR SHAPES 

4.1 Introduction 

A sphere packing treatment plan for a given brain tumor is produced in the 
first chapter. This plan can be represented numerically as a list of parameters of 
the dose spheres. In particular, the list consists of the coordinates of the dose center 
in millimeters along the lateral (Lat), anterior-posterior (AP), and axial (Ax) axes 
together with the radius of the dose sphere in millimeters. From these data, we 
can assign a unique corresponding graph by matching a sphere with a vertex and 
matching the adjacency of two spheres with an edge. Then, by using the notion of 
cutvertex, we give an order to the vertex set. We use this order to decide which edges 
to choose in order to obtain a unique maximal tree contained in the graph. 

Our main theorem of this section is Theorem 4.5.6: The perfect sequences are 
invariants of the shapes of arbitrary brain tumors. We then develop a Mathematica 
program (see Appendix B) to get a maximal tree of the graph for a sphere packing 
plan for a given brain tumor. In the near future, we plan to use this program to 
classify all the treatment plans which have been done at the Brain Institute of the 
University of Florida. We hope that the classification gives some insight about brain 
tumor shapes. 

In this chapter, we assume that a brain tumor is connected, so the graph 
representation for any brain tumor is a connected graph. 

59 



60 

4.2 Definitions and Some Properties 

Definition 4.2.1 A graph G = {V{G),E[G)) consists of a vertex set V{G) = 
{vi, . . . ^Vn} and an edge set E{G) = {ei, . . . , e^} C {{u,v}\u,v G V{G)} in which 
each edge is an unordered pair of two distinct vertices u and v, and the edge {u,v} 
is said to join u and v. For an edge {u,v} we say that u and v are adjacent 
vertices and the vertex u and the edge {u,v} are incident with each other, as are 
V and {u,i;}. From now on, |V(G')| denotes the number of vertices and |i^(G')| 
denotes the number of edges. For a vertex u G V{G), the vertex set 

Ag{u) = {v G G\v is an adjacent vertex of u} 
is called the adjacent set of u in G. 

Since there is no loop represented by a single edge, in a graph in this article, 
no vertex is adjacent to itself. 

Definition 4.2.2 We say that a graph G is isomorphic to a graph H if and only 
if there exists a bijection / : V{G) -> V{H) such that {u, v} G E{G) if and only if 
{fiu),fiv)}eE{H). 

Definition 4.2.3 A walk is an alternating sequence (uq, ^i, ui, eg, . . . , e^, Vk) of ver- 
tices and edges s.t. t;,_i j^ Vi for i = 1, 2, . . . , A;, and Cj- = {vi^i,Vi} for every i. A 
cycle is a walk (uq, ei, fi, eg, . . . , ejt,Ufc) with k > 3 in which vq = Vk is the only 
vertex repeated. A path is a walk with no repeated vertex. A (u,v)-path is a path 
with the first vertex u and the last vertex v. A (u,u)-path\s di vertex u. The length 
of the (u,v)-path, l{u,v), is the number of edges in the (u,v)-path. So the length of 
(u,ii)-path is 0. The distance d{u,v) between two vertices u and v is the length of 
a shortest path joining them, if any; otherwise d{u, v) — oo. 

Note that a path of length > 1 is of linear shape. 
Definition 4.2.4 Let G = {V, E) be a graph where V = {ui,U2, . . . ,t;„}. Then, 
for any vertex v e V, we say that Pg{v) = j if and only if 



61 

j — m'm{i G {1,2, .. . ,n}| there is a {v,Vi)-pa,th. in G}. 
We call Pg{i^) the path-value, or simply the P-value of the vertex v in G. 

Definition 4.2.5 Let G = {V, E) be a graph. For any nonempth subset V C V, 
let F = { {u,v} e E \ u,v e V } C E. For any subset F' of F, the graph 
G' = (V, F') is called a subgraph of G. A graph G is connected if and only if every 
pair of vertices are joined by a path. A graph having no cycle is acyclic. Note that an 
acyclic graph can be disconnected. A forest is an acyclic graph. A tree is a connected 
acyclic graph. An n-tree is a tree with n vertices. 

Definition 4.2.6 The degree of a vertex v, denoted by d{v), is the sum of the 
number of edges incident with v. 

Definition 4.2.7 A cutvertex of a graph is a vertex of degree greater than 2, whose 
removal increases the number of components of the graph. 

Definition 4.2.8 A nonseparable graph is connected, nontrivial, and has no cutver- 
tex. A block of a graph is a maximal nonseparable subgraph. 

Thus if V is a cutvertex of a connected graph G, then G — v is disconnected. 
Note that the traditional definition of cutvertex (usually called cutpoint in graph 
theory) does not have the degree condition. But we do not want to separate any 
linear shape subgraph into several blocks because there is no difficulty in handling 
linear shape subgraphs in our algorithm. Thus we do not call a vertex with degree 
2, a cutvertex in this chapter, even though it separates the graph. 

And if // is a block, then none of the vertices in H is a. cutvertex of H. 
Note that if there is no cutvertex in G, then the graph G itself is a block. This 
definition differs from the definition of block in Harary [5], because we have a different 
definition of cutvertex. Because of this, we have Proposition 4.2.10 below. 

Proposition 4.2.9 If a graph G is of linear shape, then the maximal tree of G is 
G itself. 



62 

Proposition 4.2.10 [5] Let v be a vertex of a connected graph G. The following 
statements are equivalent: 

(1) V separates G and d{v) > 2. 

(2) There exist vertices u and w distinct from v such that v is on every (u,u;)- 
path. 

(3) There exists a partition of the set of vertices V{G) — {v} into subsets U and W 
such that for any vertices u E U and w E W, the vertex v is on every {u,w)-path. 
Definition 4.2.11 Let G = {V, E} be a graph. For any vertex v e V we define 
the edge subset Ig{v) C E{G) by Ig{v) = {{v,u} e E{G)\ u € Ag{v)}. We call 
Ig{v) the incident edge set of v in G. 

Clearly, Ig{v) contains all the incident edges of the vertex v in G. 
Definition 4.2.12 Let G-{V,E} be a graph. For any subset F oi E we call the 
set V{F) = {v G. V{G)\ there is an edge e E F such that v and e are incident } 
the F vertex set. 

Proposition 4.2.13 [5] The following statements are equivalent for a graph T : 

(1) T is a tree. 

(2) Every two vertices of T are joined by a unique path. 

(3) T is connected and \V{T)\ = \E{T)\ + I. 

(4) T is acyclic and \V{T)\ = \E{T)\ + 1. 

Note that if a tree has n vertices, then there are exactly n — 1 edges. 
Definition 4.2.14 Let G = {V, E} be a connected graph and E' a subset of E. 
A connected subgraph T = {V, E'} is called a maximal tree of G if and only if 
T' = {V, E' U {e}} contains a cycle for any edge e E E — E'. 

Our work in this chapter produces a particular maximal tree for any given 
graph. So we have the following (well-known) theorem. 
Theorem 4.2.15 Every connected graph has a maximal tree. 



63 



Example 4.2.16 Let G be a graph with 14 vertices and 18 edges as in the figure 
4-1 below. 




Figure 4-1 



There are 3 cutvertices, 6, c, e. So the given graph G can be separated into 

6 blocks as follows: 

Gi ={VuE,} = {{a,b}, {{a,b}}}, ■" ' 

G2 = {V2,E2} = { {b,c,k,l,m,n}, 

{ {^c},{c,A;},{A;,/},{/,m},{m,n},{n,6},{6,A;},{A;,m} } }, 

G3 ={Vs,Es} = {{c,d,e}, {{c,d},{d,e}}}, 

G, ={V4,£4} = {{e,/,5}, {{e, /},{/, ^}, {5, e}}}, 

G5 ={V,,E,} = {{e,h,i}, {{e,h},{h,i}}}, and 

Ge ={Ve,Ee} = {{e,j}, { {e,j} } }. 




■• •- 
a b h c c 

Gi Gi 



d 



Figure 4-2 




64 

4.3 Graphs for Sphere Packing Plans 

The sphere packing treatment plan S having n spheres for a given brain tu- 
mor, from Chapter 1, consists of the centers, cx,C2, . . . ,c„, and the radii, ri,r2, . . . ,r„, 
of the spheres with c, = (x,, y,, 2,) for every i, where x, is for the AP coordinate, 
y, is for the Lat coordinate and Zi is for the Ax coordinate of the center, c^. (Note 
that the physicians use diameters, rather than radii, in their data sets.) 

We consider the spheres to be the vertices of a graph, and we assign the vertex, 
Ui, for the sphere centered at Cj with radius r,. Now we can assign an edge between 
two vertices if the spheres assigned by these two vertices meet. In Chapter 1, we 
noted that the collimators do not deliver clear cut boundaries for spheres-there is 
some spillover. The neurosurgeons currently assume that the portion between two 
spheres gets enough dosage of radiation if the distance between the centers of the 
two spheres is less than or equal to eleven tenths of the sum of the radii of the two 
spheres. Thus for any two vertices assigned for two spheres satisfying this condition 
we assign an edge between them. Then we have the following proposition. 

Proposition 4.3.1 Let G — {V, E} be a graph for the sphere packing plan of a 
brain tumor. For any vertices Vi and Vj in V, d{ci,Cj) < f^(''i + Tj) if and only if 
{viiVj} G E. Thus we have the following edge set; 

E = {{i,3]\d{c^,Cj) < (ll/10)(r, + rj) where i < j, i = 1,2, ...,n- 1). 

Since any brain tumor is connected in this article, there is at least one (u, v)- 
path in G for every two vertices, u and v in G. Thus we have the following propo- 
sition. 

Proposition 4.3.2 The graph G = {V, E} produced by the above method for a 
given tumor is a connected graph. 

Since we are dealing with unlabeled graphs in this article, we have the following 
proposition. , 



65 

Proposition 4.3.3 For any sphere packing treatment plan for a given brain tumor, 
there exists a unique graph that we assign to the treatment plan. 

By means of the above method, we get a unique connected graph G = {V,E} 
for the sphere packing treatment plan for the tumor. This graph does not have the 
information about the positions of the dose spheres as an aspect of the structure and 
looks only at how the spheres are attached. It is clear that the graph G does not 
have a loop or multiple edges between two vertices, since every edge is assigned for 
two different vertices which are assigned for two attached spheres. 

4.4 Order in the Vertex Set 

To get a maximal tree from a graph we may need to delete some edges in the 
graph. Thus we need to label each vertex in order to choose certain edges to delete, 
even though we are dealing with an unlabeled graph in this chapter. So there is no 
specific meaning for this labeling except that it is only used to choose a maximal tree 
for the graph. 

Example 4.4.1 Let P be the sphere packing treatment plan (see Figure 4-3) for a 
given brain tumor. 




Figure 4-3 

Then, by Proposition 4.3.3, there is a unique graph G for the sphere packing plan. 
The graph is given below in Figure 4-4. 




Figure 4-4 



66 

There are two difTerent isomorphism classes, namely Ti and T2, of maximal trees 
for the graph G. That is, we could choose either of these for a maximal tree to assign 
the graph G. Since, in our algorithm, we want to get the same maximal tree for a 
given graph every time, we need certain rules to get the same tree. (See Figure 4-5.) 




Ti T2 

Figure 4-5 



In this chaper, the graph comes from a sphere packing treatment plan. That is, 
the main shape of the brain tumor depends on the size of spheres and the connection 
between spheres. Even though we cannot keep the information about the size of 
spheres in the graph, it seems to us that the bigger the sphere is, the more it has a 
chance to get attached to more spheres. So we assume that the larger degree vertices 
play a more important role in classifying the tumor shapes into trees than the smaller 
degree vertices. That is, by choosing a largest degree vertex first, the shape of the 
tumor is apparently most closely preserved. Thus, in the previous example, we choose 
the vertex q or s as the starting vertex; then we pick all the incident edges. Then 
we get the tree Ti . Therefore we want to choose the tree Ti for the maximal tree of 
G. Note that the tree T2 produces a linear graph which does not show the shape of 
the tumor as closely as Ti. 

But there are some vertices which are more important than the bigger degree 
vertices. Recall the graph G in Example 4.2.16. Then, in the block 6*2, it is clear 
that the vertex k has the largest degree, 5. But the cutvertices, 6 and c, play a 
critical role in obtaining a maximal tree of G. So, to get a maximal tree for a graph 
G, we want to start at the cutvertices of G first, instead of the vertices with the 
largest degree. So we want to label the cutvertices first. On the other hand, there 



67 


are difFerent kinds of 'cutvertices' in some graphs. The following example shows such 


a case. 


Example 4.4.2 Let G = {V, E} be the graph in Figure 4-6. 


Wg 


Un. ^10/ \u8 


"11 • 




\ X 


"3 

11 ^ ^ \ 






U2 U4 


Figure 4-6 


Then there are two cutvertices of the graph G, namely U2 and Uiq. Us- 


ing these two cutvertices, the graph G is separated into four subgraphs, namely 


Gi, G2, G3 and G4. (See Figure 


4-7.) 





G^ 



Ull- 



U\Q Uio UlO 




- -' T = • , 



G3 




«2 W2 

Figure 4-7 



Then the subgraphs Gi, G2, and G3 are blocks, but the subgraph G4 con- 
tains its own cutvertices, U4 and Us, which are not cutvertices of the graph G. We 
separate the subgraph G4 into four subgraphs by using its cutvertices U4 and ug. 



68 

(See Figure 4-8.) Note that there is no specific order in labeling the subgraphs. So 
at this moment, we relabel the subgraphs of G hy Hi, H2-, ■ ■ ■ , Hf. 



"a* 




.,: «4 U4 

Figure 4-8 

Then, again, the subgraphs i/i, H2, ■ ■ ■ , He are blocks, but the subgraph Hr 
contains its own cutvertex, uq, which is neither a cutvertex of the graph G nor a 
cutvertex of the subgraph G4. We separate this subgraph Hr into two subgraphs by 
using ue. (See Figure 4-9.) And we relabel the subgraphs of G by Bi, B2, ..., Bg. 

Therefore {^2,^^10} is the set of cutvertices of the graph G. But {^4,^8} is 
the set of the cutvertices of a subgraph which is produced after the first separation 
using the cutvertices of the graph, and ug is the cutvertex of a subgraph which is 
produced after the second separation. 

For the purpose of labeling the vertices in a graph, we separate these cutvertex 
sets for different levels, from each other. 

Definition 4.4.3 Let G be the graph assigned for a given sphere packing plan 
P. Then the vertex set V{G) of the graph G is the union of two disjoint subsets, 
namely Ci{G) and C'i{G), where Ci{G) = {v e V{G)\ v is a cutvertex of G} 



69 

and Ci^(G) = V{G) - Ci{G). We call Ci(G) the first step cutvertex set of G. For 
every i — 2,3, . . . , |V(G)|, we define a subset Ci{G) of Cf_i(G) as the collection 
of the vertices of C?_i(G), which are cutvertices of a subgraph produced after the 
(i — l)-th separation using the elements of Cj_i(G). Then we call C,(G) the i-th 
step cutvertex set of G, and let C^{G) = C-_^{G) — Ci{G). We assume that there 
are finitely many vertices in a given graph. If there exists at least one cutvertex, 
then there exists an integer 1 < fc < n such that Ci{G) ^ for every i < k, and 
Ci{G) = for every i > k + 1. Then we call k the separation step constant of the 
graph G, and let C%G) = {CkYiG). 

If there is no cutvertex of G then the graph is a block, and we say that the 
separation step constant of G is 0. 




U4 U4 

Figure 4-9. 



Proposition 4.4.4 Let \V{G)\ = n and let the separation step constant of G be 
k > 0. Then there is a sequence of integers {mi, m2, . . . , ruk} with < mi < m2 < 
...<mk such that |Ci(G)| = mi, and \Ci{G)\ = nii - m^_l, for i = 2,3, . . . ,k. 



70 

Proof Since A; > 0, the first step cutvertex set Ci{G) is not empty. Thus there is 
a positive integer, namely mi, such that |Ci(G)| = mi. For every i = 2,3, ...,A;, 
let rrii = mi_i + |C,(G')|. For every z = 2, 3, . . . , A;, the i-th step cutvertex set C,(G) 
is not empty. So we have that m{ > m,_i, and |C,(G)| = rrii — rrii-i. J_ 

Now we label the vertices as follows; 

(1) the vertices in Ci{G) are labeled by {1, 2, . . . ,mi}, 

(2) for every i = 2,3, . . . , A;, the vertices in Ci{G) are labeled by {mj_i + l,mj_i + 
2, . . . ,mi — l,mi}, and 

(3) the vertices in C'^{G) are labeled by {ruk + 1, m^ + 2, . . . , n}. 

We arbitrarily name the vertices of C,(G) and C"'(G), and denote that Ci{G) 
= {ui,U2,. ..,Umi}, Ci{G) = {um,_i+i,iim._i+2,-- • ,w„j,} for ? = 2, 3, . . . , A), and 
C^IG) = {umi,+i-,Um^+2, ■ ■ ■ ,Un}. It is clear that for every vertex Up G Ci{G) and 
every vertex Ug G Cj{G) with i ^ j, we have that -p < q \{ and only if % < j. 
And also, for every vertex Up 6 Ci{G) for every z = 1,2, ...,A;, and every vertex 
Ug 6 C'^(G), we have that p < q. Assume that, for every vertex u,-, the center and 
the radius of the sphere which is assigned to that vertex Ui, are Cj = {x,-,y,, 2,} and 
r,-, respectively. 

We now relabel the elements for each of the sets, Ci(G), C2{G), ..., Ck{G) 
and C'^{G), in the following way: 
for every pair of vertices, Ui,Uj, in one of Ci{G),C2iG), . . . ,Ck{G) and C"=(G), 
i < j if and only if 
(i) d{ui) > d{uj); or 

(ii) If d{ui) = d{uj), then r,- > rf, or ' 

(ii) If d{ui) = d{uj) and r,- = r^, then Xi < Xj\ or 
(iii) If d{ui) = d{uj), Vi = r^, and a;,- = Xj, then j/, < y^; or 
(iv) If (/(u,) = d{uj), r, = Tj, a;, = Xj, and t/, = y^, then 2,- < z^-. 
Note that d{ui) represents degree of the vertex Ui in G. 



71 

It is clear that for any two different spheres, at least one of the coordinates is 
different. Thus any two distinct spheres can always be compared by the above order. 
Therefore the above order for the vertices of the graph is well defined. 

4.5 Maximal Tree from a Graph 

In this section, we develop an algorithm that will uniquely select a maximal 
tree from the graph which is produced for a given brain tumor. The choice is made 
so that the tree will most closely resemble, in our opinion, the shape of the tumor - 
that is, of the graph obtained for the tumor. 

Let G = {V, E) be the graph for a given sphere packing plan. Let V{G) = 
{ui,U2, . . . , u„} for some positive integer n, where all the vertices in V are labeled 
by the method in the previous section. 

Define a subgraph To = {V{G),Fo) with ^(^0) = V ^ V{G) and Fq = 
0; that is, there is no edge in Tq. Then, for every i = 1,2, ...,n, we have that 
Pjoi'^i) = i- (See Definition 4.2.4.) 

(1) For the vertex ui, let Fi = Fq U Ig{ui). (See Definition 4.2.11.) Let Ti = 
(!/((?), Fi). The subgraph (V(Fi),Fi) C Fi is a tree. Thus, if V{Fi) = V{G), then 
Fi = {V{G), Fi) = (V'(Fi), Fi) is our maximal tree of G. Note that for every vertex 
V eV{Fi) we have that Pti{v) = 1, and for every vertex Uj V{Fi), we have that 
Ptx{uj)=3. 

(2) Assume that V(Fi) 7^ V{G). For the vertex U2, there are two cases, that is, 
Pti{u2) = 1 and Fti(u2) = 2. Now define the edge subset Ig{u2) by /G(ii2) = 
Ig{u2) - {{U2,v} G E\ Pt,(v) = 1}. 

(a) If Ft, (■"2) = 1, that is, there is a (ui,W2)-path in the subgraph Fi, then let 
F2 = FiU/^(h2). Each edge in the set {{u2,v} e E\ Pr.iv) = 1} = {{u2,v} e E\v e 
V{Fi)} makes a cycle with {ui,U2} and {ui,v}, since Pt^M = 1. Thus there is 
no cycle in the subgraph (V(F2),F2), so it is a tree. Let F2 = {V{G),F2) C G. 



72 

If V{F2) = V{G), then T2 = iV{G),F2) = {V{F2),F2) is our maximal tree of G. 
Note that for every vertex v G ^(^2) we have that Pxiiv) = 1, and for every vertex 
II J ^V{F2) we have that PtjC^^j) = j- 

(b) If Pti{u2) — 2, then there is no (?ii,U2)-path in the subgraph Ti. 
(i) Ifthere is a non-empty subset {m2i, ^22, • • • , W2J C V(/g(^^2)) where Pt^{u2,) 
= 1 for « = 1, 2, . . . , i and 2, < 2^ for 1 < z < j < i!, then let F2 = FiD I'g{u2) U 
{{u2,U2,]]. Then the subgraph (V(F2),F2) C G is a tree. Let T2 = {V{G),F2) C 
G'. If y(F2) = V{G), then r2 = {V{G),F2) = {V{F2),F2) is our maximal tree of 
G. Note that for every vertex v € V{F2) we have that Pxiiv) - 1, and for every 
vertex u^ ^ ^^(^2) we have that Pr^iuj) = j- 

(ii) If none of the vertices in V{Ig{u2)) has p-value 1, that is, for every vertex 
V e V{Ig{u2)) there is no (ui,u)-path, then let F2 = FiU IgM- Since PtA^) = 1 
for every vertex w E Fi and Pt,{v) = 2 for every vertex v G Ig{u2), the subgraph 
(V(F2),F2) is a forest, but not a tree. Let T2 = {V{G),F2) C G. It is clear that 
the subgraph T2 cannot be our maximal tree, even if we have that V{F2) = V{G), 
because the subgraph T2 is disconnected. Note that for every vertex v € ^(^2) = 
ViFi U IgM) = V{Fi) U V(/g(u2)) we have that Pt,{v) = 1 if y G V(Fi), and 
Pxiiv) = 2 if u 6 V{Ig{u2)). And, for every vertex Uj ^ V{F2), we have that 
PTiM =j. ■■■■■ ■ - - 

(3) By induction, at the j-th step, the subgraph T,_i = (y(G),F,_i) has been 
defined. We want to define the subgraph T, C G. For the vertex u^, there are two 
cases, that is, Pt^_,{uj) = j and Pt^_,{u^) = q for some 1 < q < j. For every 
2 = 1, 2, . . . ,n, define 

m,_i(i) = mm{/e {1,2, ... ,n}\PT^_^{ui) = i ^ind m E Ag{u,) }. 
If the set {/ E {l,2,...,n}\ui € V{Ig{uj)) and Ft,_,(w/) = z } is empty, then the 
vertex Um^_^^i) is not defined. So there is no edge {uj,Um _,{{)}. 



73 



(a) Let /V,_, {uj) = i; that is, for every i = 1, 2, . . . , j — 1, j + 1, . . . , n, there is 
no (uj,Ui)-path in the subgraph Tj_i = (y(G),F,_i). Let 

f; = i^,_iu(ur=i{K,ti„^_,(,)}}). 

Then the subgraph {V{Fj),Fj) is a forest. Let T, = (y(G),F,) C G. If 1/(F_,) = 
V{G) and |V(f;)| = |F,| + 1, then, by Proposition 4.2.13, the subgraph Tj = 
{V{G), F,) = {V{Fj), Fj) is our maximal tree of G. 

(b) Let Ptj_^{uj) = q for some I < q < j, that is, there is a (u,,?ij)-path in the 
subgraph r;_i =(]/(G'),F_,_i). Now let 

F, - F,_i U (Uf^i, ,.^J {u„ii„^_,(,)} }) . 
Then the subgraph (y(F,),F,) is a forest. Let Tj = {V{G),Fj) C G. If V{Fj) = 
V{G) and \V{Fj)\ = \Fj\ + 1, then by Proposition 4.2.13, the subgraph Tj = 
(V(G'), Fj) = {V{Fj), Fj) is our maximal tree of G. 

Note that if u is an z'-th step cutvertex, then d{u) in G is same as d{u) in 
T,_i. Also note that, for every i = l,2,...,n, {ui, ua, . . . ,«,} C V(Fi), that is, 
V(G) = V(F„). We will see in Theorem 4.5.3 that 7; = (K(G),F„) = (y(F„),F„) 
is our maximal tree of G. By the Tree Classification Theorem (Theorem 3.6.8), this 
tree F„ can be denoted by a unique perfect sequence. 

Example 4.5.1 Let G = {V,E) be a graph where V = {wj, U2, . . . ,««}, which 
are ordered as in the previous subsection, and F = {ei, 62, . . . , 613} as in the figure 
below. Clearly, the graph G does not have a cutvertex, so the order is decided by 
only the sizes of the spheres and the coordinates of the centers of the spheres. 



"8 ei3 U7 62 Ui 



y.3' 



e-r/ 


/\ 


\eio 


\ 


\ei2 y 


/ 




e& 




es 


y^b 




h\ 


\/ 


/e4 \ 


\/ 


/eii 





U2 eg ue 

Figure 4-10 





















74 


Let 


To = {V{G), 


Fo) 1 


oe a subgraph of 


J — 


(y,E) where Fq = 0, 


as shown 


in 


Figure 4-11. 


























• 




tt7 

• 


• 












U3» 


tl2 


W4 

• 


• 
«8 


•^^5 
















Figure 


4-11 








Since 


IgM 


= {ei 


,62}, 


let Fi = 


FoUlaiu 


1) = 


{ei,e2}. Then V{Fi) = 


{ui,U5,U7}. 


Since 


n^i) 


= {U] 


,^5, 


uj} ^ V{G), the t 


ree 1 


V{Fi),Fi) is not a maximal tree 


of 


G. Let Ti = 


iV{G),F, 


which is 


shown in 


Figure 4-12. 














Us 

• 




U7_ 


62 Ui 












«3. 


• 


tl4 

• 


• 


•^5 










.. 




"2 




tt6 









Figure 4-12 

We have that mi(i) = i for i = 1,2,3,4,6, and 8, but mi (5) and mi(7) do not 
exist. Since Pti{u2) = 2 and AqM = {u3,U4,ue}, let 

i^2 =FiU(U=3,4,6{K,liJ}) '■ 

= i^l U /g(w2) 

= {ei, 62} U {63, 64, 65} = {ei, 62, 63, 64, 65). 
Then ^(Fs) = {uj, ug, 1*7,^2, W3, ^4,^6} / V^fC) and the subgraph (V(F2),F2) is a 
forest, not a tree. Thus it cannot be a maximal tree of G. Let T2 = {V{G),F2). 
(See Figure 4-13.) 



• I, ■ 1 



yju '. <^-V^L . i H 



75 




Figure 4-13 



Note that Pt,{ui) = Pt,M = Pt,{u,) = 1, Pt,{u2) = Pt.M = Pt.M = 
Pt2{u6) = 2, and Pr^ius) =8. Thus we have that m2(l) = l,m2(2) = 2, m2(8) = 8. 
Note that m^ii) does not exist for i = 3,4,5,6,7. Since ui ^ A{u3) and Pr^ius) - 
2, weget /^3 = ^2U{{?i3, Ms}} = {61,62,63,64,65,67}. Since the subgraph (y(f'3),F3) 
is a forest, but not a tree, it is not a maximal tree of G. Define T3 = {V{G),F3). 
(See Figure 4-14.) 




U2 65 ue 

Figure 4-14 

Note that PtA^i) = ^73(^5) = PnM = 1 and ^73(^2) = PtsM = Pni^d = 
Pn{u&) = Pr^ius) = 2. Thus we have that 7713(1) = 5 and 7713(2) = 4. Note that 
m3{i) does not exist for i = 3,4, ...,8. Since Pt-^^u^) = 2, we define F^ = F^iJ 
{{u4,U5}} = {61,62,63,64,65,67,68}. Since ViF^) = {vi,V2,. . . .v^] = V{G) and 
\V{F4)\ = 8 = IF4I + 1, the subgraph T = iV{F^), F4) is a maximal tree of G. (See 
Figure 4-15.) 



76 



r'Mi^4r^^.,r■: 




U2 65 ue 

Figure 4-15 

At this moment, we have that Pt{ui) = Pjiu^) = . . . — Pt{us) = 1. Then, 
for every iit G V{G) with t > 4, we have that Ft = F4. Thus, for every t > 4, the 
subgraph {V{Ft),Ft) is same as T = (V(F4), F4). 

The next example shows how we get the maximal tree for a given graph 
containing some cut vertices. 

Example 4.5.2 Let G be the graph in Example 4.2.16. (See Figure 4-1.) Then 
Ci{G) = {6,c, e} and Q(G) = {a,d, f,g,h,i,j,kj,m,n}. In Ci{G), we have that 
d{e) = 5, d{b) = 4 and d{c) = 3. On the other hand, in C^iG), we have that 
d{k) = 5, d{m) = d{n) = 3, d{d) = d{f) = d{g) = d{h) = d{l) = 2, d[a) = d{i) = 
d{j) = 1. And C2 = 0. Thus we order the vertices as follows; vi = 6, V2 — b, V3 = c 
and V4 = k, {v5,ve} = {m,7i}, {^7,^8,^9,^10,^11} = {dj,g,hj}, {^12,^13,^14} = 
{a,ij}. Assume that V5 = m, vg = n, Vr = d, Vs = /, vg = g, v^ = h, Vn - 
/, Vx2 = a, Vi3 = i, ui4 = j, which are decided by the sizes and centers of the 
corresponding spheres. (See Figure 4-16.) 




VU V2 V3 V7 



Figure 4-16 



^13 



t^io 




Vi Vs 



Vu 



77 

Since Ig{vi) = { {^'1,^7}, {^'b^s}, {^1,^9}, {vi,t;io}, {^1,^^14} }, let Fi = Ig{vi). 
Then V(Fi) = {vuVj^vs^v^^vio^vi^}. Since V{Fi) # ^(G), the tree T^ = (V(G),Fi) 
is not a maximal tree of G. Thus, for the cut vertex vi, we have the following sub- 
graph which is Ti = {V{G),Fi). (See Figure 4-17.) 



V5> 



vn 



^^13* 



Ve' 



V4 



U12 V2 V3 V7 



Figure 4-17 




Since Pti{v2) = 2, and, for every vertex v € Ag{v2) = {^^3,^^4,t^6,t^i2}, ^ri(^^) 7^ 1, 
let F2 = Fi U Ig{v2). The subgraph (1/(^2), F2) is a forest, but not a tree. Thus it 
cannot be a maximal tree of G. Now, for the cutvertex V2, we have the following 
subgraph which is T2 = {V{G),F2). (See Figure 4-18.) 



V5' 



Vn 



t^l3' 




Figure 4-18 



Since ^0(^3) = {t^2,i^4,^^7}, PtA^2) = PtA^a) = 2 = Pt^v^), and PtA^j) = 1, let 
F3 = F2 U {{vj^vj}]. Then, for the cutvertex U3, we have the following subgraph 
which is {V{F^),F^). Then the subgraph {V{F^),F^) is a tree. But V{F3)^V{G). 



78 

Thus it cannot be a maximal tree of G. We have the following subgraph which is 
T3 = {V{G), F3). (See Figure 4-19.) 



V5» 



vn 



Vl3» 




V12 V2 V3 Vj 



Figure 4-19 



Since Ag{v4) = {v2,V3,V5,Ve,Vn}, ^nd 

Pn{v2) = PtAv^) = Pt,{v^) = 1 = Pn{v4),PTAv5) = 5,Pt,{vu) = 11, 
we define i^4 = F3 U {{1^4,^5}} U {{^4,^11}}- Then the subgraph {V{F4),F4) is a 
tree. But V{F4) ^ V{G). Thus it cannot be a maximal tree of G. Then, for the 
cutvertex V4, we have that the following subgraph which is T4 = {V{G),F4). (See 
Figure 4-20.) ;' ;^ v . 



! • »,f = 



•^^R 




^^13« 



W12 V2 V3 vr 



Figure 4-20 




For the vertices V5,Ve,V7,V8,VQ, there is no 'new' edge. Thus we get the same sub- 
graph as above, that is, T4 = T5 = Te = T7 ^ Ts = Tg. But, for the cutver- 
tex vio, we have that V13 G V{Ig{vw)) and PtA^is) = 13 7^ 1 = Pt,{vio)- Thus 



79 

Fio — FqU { {^10,^13 } and ViFio) = V{G). Therefore we have the following sub- 
graph which is r = (y(G), Fio) = (V(Fio), Fio). (See Figure 4-21.) 




Ul2 V2 U3 V7 



Figure 4-21 



Ul4 



Clearly, the subgraph T = {V{Fio), ^lo) does not include a cycle. Thus it is a max- 
imal tree of G. That is, for every t = 11,12,13,14, we have that {V{Ft),Ft) = 
iV{Fio),Fio). Therefore, the subgraph T = {V{Fio), Fw) = {V{G), Fw) is the max- 
imal tree of the graph G. 

For this resulting tree T = (V(i^io), Fio), choose a vertex sequence s by 
s = {vi,V7, V3, U2, V4, V5, ^11,^6, ^12, 'Wio, ^^13, ^8, ^9, Vu) ■ Then the sequence 

P = (5,1,1,3,2,0,0,0,0,1,0,0,0,0) 
is the degree sequence of s. By Theorem 3.4.12, P satisfies DSC. It is clear that 
P also satisfies DSbC. By Corollary 3.6.10, P is the perfect sequence for the tree 
T = iViFio),Fio). 

Theorem 4.5.3 Let G — {V, E} be a graph for a sphere packing plan where 
V = {ui,U2,...,Un} with the order described in Section 4-4- Let the subgraph 
(V(F„),F„) of G come from the above procedure. Then V(F„) = V{G). There- 
fore (V(F„), F„) is a maximal tree of G and there is a unique perfect n-sequence for 
the tree (y(F„),F„). 

Proof The subgraph (1/(F„),F„) is connected. In fact, assume that the sub- 
graph {V{Fn),Fn) contains two disjoint subtrees, namely Tj and T2. Then the 






'•{VtH 



80 

path-value for every vertex in Ti is diflferent from the path-value for every ver- 
tex in T2. Since the graph G is connected, there is at least one edge e € E{G) 
which connects the two subgraphs Ti and T2 and e ^ E{Ti U T2) = F„. Let 
{ {vj^ ,Vk^}, {uj2, Vkj},- ■ ■, {vj^, Vkg} } be the collection of such edges where Vj^ G Ti 
and Ufc, € ^2 for i = 1,2,. . . ,q. Without loss of generality, let ji < ji for every 
i = 2, 3, . . . , <?. Then it is clear that {vj^ , uaii } G Fj^ by the procedure of getting the 
subgraph (y(i^„),F„). Then {vj^,Vk^} € i^„. This is a contradiction. Therefore the 
subgraph (y(F„),F„) is connected. The path-value in the procedure of getting the 
subgraph (V'(F„),F„) guarantees that the subgraph (V(F„),F„) is acyclic. There- 
fore {V{Fn), Fn) is a tree. It is clear that, for every i — 1,2, ... ,n, the vertex set 
V{Fi) contains the vertices Ui,U2,. . . ,Ui. Thus V[Fn) contains all the vertices of 
G, since V{Fn) D {ui,U2, . . . ,Un} = V{G). That is, V{Fn) = V = V{G). Hence 
the subgraph (y(F„),F„) is a maximal tree of G. By the Tree Classification The- 
orem (Theorem 3.6.8), it is clear that there is a perfect n-sequence for the tree 

(y(F„),F„). ± 

Definition 4.5.4 The tree shape of a brain tumor is the tree corresponding to that 
tumor, or equivalently, its unique corresponding perfect sequence. 

Definition 4.5.5 Two tumors have the same shape if and only if their corresponding 
graphs obtained from their respective sphere packing plans are the same. 

As in Chapter 2, for any brain tumor, we have a unique sphere packing plan 
which can be denoted by a graph. From the previous theorem, we have a unique 
perfect sequence for the graph. That is, we can assign exactly one perfect sequence to 
each brain tumor. So, if two perfect sequences are distinct, then their corresponding 
trees, and therefore their respective corresponding graphs and sphere packings, are 
also distinct. That is, if two tumors are represented by distinct perfect sequences, 
then their corresponding trees are not isomorphic. And their respective graphs and 



81 

sphere packing plans are not isomorphic. Thus, we may consider their shapes to be 
distinct. Therefore we have the following as our main theorem of this section. 

Theorem 4.5.6 The perfect sequences are invariants of the shapes of arbitrary brain 
tumors. 

4.6 Graph from a Maximal Tree 

Let r = { V, £■'} be a maximal tree for a graph G = {V, E} which is obtained 
from the sphere packing plan of a given tumor or solid shape. We observe that we can 
recover the original graph, G, from T. Since V{T) = V = V{G) and E{T) = E' C 
E = E{G), we need to add the remaining edges to the edge set of the maximal tree to 
get the graph G. Since the graph G comes from the sphere packing treatment plan, 
each vertex w in G denotes a sphere of the sphere packing plan. Thus, for every 
vertex u,- 6 G, let c, = {xi,yi,Zi) and r^ be the center and the radius of the sphere. 
By Proposition 4.3.1, for any two vertices v, and Vj in V if d{ci,Cj) < ^{ri + rj), 
then the edge {vi,Vj} is in the edge set, E{G), of the graph G. Thus 

E'U{{vi,v,} eVxV\ d{c,,c,) < i^(r, + r,)} = E. 
Therefore we get the graph G = {V,E}. 

4.7 Algorithm for Our Maximal Tree 

Let G = {V,E) be the graph for a sphere packing plan with \V\ — n. 
STEP A Find all the i-th step cutvertices of the graph G, for 1 < i < n. 
STEP B Label the vertices in the vertex set V by the order explained in Section 
4.4. 

STEP C By induction, for each i = l,2,...,n, get the subgraph {V{Fi),Fi) of 
G. Then T = (V'(F„),F„) is our maximal tree. 



APPENDIX A 
SHELLING PROGRAM FOR SPHERE PACKING 

In this appendix, we provide the C++ program we developed to get the sphere 
packing plan for a given tumor shape. The first section shows the program translating 
the data from CT scan to the data of appropriate form for the main program, which 
is in the second section. Note that this program does not include the score function 
which was developed by Thomas Wagner. We refer the reader Appendix E for the 
complete article on the sphere packing treatment plan. 



A.l Program for Data Reading 

// rewrite data file into x,y,z format 

// & produce the total # of data, x,y,z min & max 

#include <iostream.h> 
#include <f stream. h> 
#include <iomanip.h> 
#include <stdlib.h> 
#include <math.h> 

mainO 

{ const int nofdata=3370; // comes from data003.txt 

int xposit ion [nof data] , yposition[nofdata] , zposition[nofdata] ; 

int q; 

float a; float b; float c; 

int k=0; 

{ ifstream inClientFileC'dataOOS.txt", ios::in); 



while (inClientFile >> a >> b » 
{ xposition[k] = int (floor (a)) 
yposition[k] = int (f loor(b)) 
zposition[k] = int (floor (c)) 
k++; 
} . 



c) 

// check the number 

// check the number 

// check the number 



int xmin' 
int xmax^ 
int ymin^ 
int ymax: 
int zmin- 
int zmax: 



=xposition[0] 
=xposition[0] 
=yposition[0] 
=yposition[0] 
=zposition[0] 
=zposition[0] 






for (int i=0; i<nofdata; i++) 
{ if ( xposition[i] < xmin ) 
xmin = xpositionEi] ; 



82 



83 



else if ( xposition[i] > xmax ) 

xmax = xposition[i] ; 
else if ( yposition[i] < ymin ) 

ymin = yposition[i] ; 
else if ( yposition[i] > ymax ) 

ymax = yposition[i] ; 
else if ( zposition[i] < zmin ) 

zmin = zposition[i] ; 
else if ( zposition[i] > zmax ) 

zmax = zposition[i] ; 




setw(5) 



cout « nofdata << setw(5) << xmin << setw(5) << xmax 
<< setw(5) << ymin << setw(5) << ymax << setw(5) 
<< zmin << setw(5) << zmax; 

cin >> q; 



.-.- Program for Center Searching 

// searching the centers for pat 2 



A. 2 



#include <iostrecLm.h> 
#include <f stream. h> 
#include <iomanip.h> 
#include <stdlib.h> 
#include <math.h> 



crnoH ^i-^%x 



int square (int) ; 

int MAX (int, int, int ) ; 

mainO 

{ const int nofdata=3370; 

const int xmin = -32; 

const int xmax = -4; 

const int ymin = -29; 

const int ymax = 4; 

const int zmin = -57; 

const int zmax = -37; 

const int xfix = 1-xmin; 
const int yfix = 1-ymin; 
const int zfix = 1-zmin; 



// function prototype 
// function prototype 



// check the number from mM003.txt 

// check the number 

// check the number 

// check the number 

// check the number 

// check the number 

// check the number 



int xposition [nofdata] , yposition [nofdata] , zposition [nofdata] ; 






int q; 

float a; float b; float c; 

int k=0; 

{ ifstream inClientFile("data003.txt", ios::in); 
while (inClientFile » a » b » c) 
{ xposition[k] = int (f loor(a))+xf ix; 
yposition[k] = int (f loor(b))+yf ix; 
zposition[k] = int(f loor(c))+zf ix; 
k++; 
} 
} 

const int x = xmax - xmin + 3; 

const int y = ymax - ymin + 3; 

const int z = zmax - zmin + 3; 

const int nc = x*y*z; // number of cells 

int cc[nc]; // status value 

for (int i=0; i<nc; ++i) 
ccCi] = -3; 

int xc[nc]; // x-coord. of c[nc] 

int yc[nc]; // y-coord. of c[nc] 

int zc[nc]; // z-coord. of c[nc] 

// setting the x,y, z-coord. for each cell 
for (int i=0; i<nc; i++) 
{ zc[i] = floor(i/(y*x)); 

xc[i] = floor((i-zc[i]*y*x)/x) ; 

yc[i] = i-zc[i]*y*x-xc[i]*x; 

// setting the boundary of tumor by -1 

for (int i=0; i<nofdata; i++) 

{ cc[zposition[i]*x*y + xposition[i] *y + yposition[i]] = -1; 

// setting the initial of normal by 
cc[0] = 0; 

// setting the normal cell by 
int h=0; 

for (int j=0; j<x*y; j++) 
{ for (int i=0; i<nc; i++) 
■C if ( cc[i] == -3 ) 

{ if (cc [i-1] ==0 I I cc [i+1] ==0 I I cc [i-y] ==0 I I cc [i+y] ==0) 
{ cc[i] = 0; 

h++; 
} 

else; 
} 

else; 
} 





85 


if (h==o) ,. „.,:^..virr-v;.,: 




break; * •-•..-.. 




else ,.„ ,, . , ► ■ ■ ; \ 




h=o; l^lr--. -- ".' ^ 




} 




^^■- r -:,' r:'/'.; i 




// setting the remaining tumor cell by -2 




for (int i=0; i<nc; i++) // checking 




{ if ( cc[i] == -3 ) // checking 




cc[i] = -2; // checking 




else; // checking 




} // checking 




// setting the boundary cells 




int maxrad; 




int nof maxrad; 




for (int j=0; j<=MAX(x,y,z)/2+l; j++) 




{ int k=0; 




for (int i=0; i<nc; i++) 




{ if (cc[i] == -1 II cc[i] == -2) 




{ k++; 




if ( cc[i-l] == j II cc[i+l] ==j II cc[i-y]==j 




II cc[i+y]==j II cc[i-y*x]==j I I cc[i+y*x]==j ) 




{ ccCi] = j + 1; 




nof maxrad = k; 




} 




else; 




> ... 




else; 




} 




maxrad = j ; 




if (k==0) ,.. ■ , 




break; ■ , - 




else; 




} 




// checking the no . of nof maxrad 




// if nof maxrad > 100, then you have change the number 




if (nofmaxrad >100) 




{ cout « endl « endl « endl « endl « endl « 




« endl « endl « endl « endl; 




cin >> q; 




} 




else; 




// pick the boxes with maxrad 




int suprad[lOO] ; 




int TotalNofBox4[lOO] ; ■; 




int TotalNofMax=0; 




for (int i=0; i<nc; i++) 




{ if (cc[i]==maxrad) 





86 



4 



} 



{ suprad[TotalMof Max]=i; 
TotalNofMax++; 

\ 

else; ' : • 5 



cout « TotalNofMax « endl; 
cin >> q; 

// Count for the number of centers of each case 
for (int k=0; k<TotalNofMax; k++) 
{ // reset TotalNofBox4[ ] to 

for (int i=0; i<100; i++) 

{ TotalNofBox4[i] = 0; 

} 

TotalNof Box4 [maxrad] ++ ; 

int tcc[nc]; // temporary cell notion 

for (int i = 0; i<nc; ++i) 

tccCi] = cc[i]; // reassign tcc[i] for 'for' loop 

// remove the biggest sphere 
for (int p=0; p<nc; ++p) 

{ int dist = floor(sqrt( square (yc[suprad[k]]-yc[p]) 

+ square (xc [suprad [k] ] -xc[p] ) 
+ square (zc [suprad [k]]-zc[p]) )); 
if ( dist < maxrad ) 

tcc[p] =0; 
else; 
> 

// setting the remaining tumor cell by -2 
for (int i=0; i<nc; i++) 
{ if ( tcc[i] >= 1 ) 
tcc[i] = -2; 
else; 
} 

// setting the boundary cells 

for (int j=0; j<=MAX(x,y,z)/2+l ; j++) 

{ int 1=0; 

for (int i=0; i<nc; i++) 
{ if (tcc[i] == -2) 
{ if ( tcc[i-l] == j II tcc[i+l] ==j II tcc[i-y]==j 

II tcc[i+y]==j II tcc[i-y*x]==j || tcc[i+y*x]==j ) 
{ tcc[i] = j + 1; 
++1; 

> 

else; 

} ■ , 

else; 

> 
if (1==0) . ' 

break; 



87 



else; 
} 

// check if there is more maxrad pixcel 
for (int i=0; i<nc; i++) 

{ if ( tcc[i] == maxrad ) • , . 

{ cout « endl « endl << endl « 

" WARNING! ! ! WE HAVE MORE 'MAXRAD' PIXCEL AT (" 

« xc[i] « "," « yc[i] « "," « zc[i] « ")' 
« endl; 
cin >> q; 
break; 
} 
else; 



//remove the smaller or = sphere 
for (int j=maxrad-l; j>l; — j) 
{ for (int i=0; i<nc; ++i) 
{ if ( tcc[i] ==j ) 

{ TotalNofBox4[j]++; 
// remove the sphere 
for (int 1=0; Knc; ++1) 
{ int dist = floor(sqrt( square (yc [i] -yc[l]) 

+ square (xc [i] -xc[l] ) 
+ square (zc[i]-zc[l]) )); 
if ( dist < j ) 
tcc[l] = 0; 
else; 
} 

// setting the remaining tumor cell by -2 
for (int i=0; Knc; i++) 
{ if ( tcc[i] >= 1 ) 
tccCi] = -2; 
else; 
} 

// setting the boundary cells 
for (int j=0; j<=MAX(x,y,z)/2+l; j++) 
{ int 1=0; 

for (int i=0; Knc; i++) 
{ if (tcc[i] == -2) 
f { if ( tcc[i-l] == j I I tcc[i+l] ==j II 

tcc[i-y]==j II tcc[i+y]==j || 
, ,v tcc[i-y*x]==j II tcc[i+y*x]==j ) 

' ■ { tcc[i] = j + 1; 

++1; 

} 
else; 

> 
else; 

} 

if (1==0) 
break; 



} 



88 

else; 

} ■; 

} 

else; 
} 
} 

// output the result of centers 

{ of stream outClientFile( "pat003-Nof Centers .txt", ios::app); 
{ outClientFile « endl « endl « endl « endl « endl « 
(k+1) « setw(5) « "(" « (xc[suprad[k]]-xfix) « "," 
« (yc[suprad[k]]-yfix) « "," « (zc[suprad[k]]-zf ix) 
<< ") with radius = " << maxrad << endl; 
} 
} 

for (int j=maxrad; j>l; j — ) 

{ of streajn outClientFile("pat003-Nof Centers. txt" , ios::app); 
{ outClientFile « setw(4) « j « setw(4) 
« TotalNofBox4[j] « endl; 
} 
} 



// Search for centers 
for (int k=0; k<TotalNofMax; k++) 

{ int tcc[nc]; // temporary cell notion 

for (int i = 0; i<nc; ++i) 

tcc[i] = cc[i]; ^ // reassign tcc[i] for 'for' loop 

// output the result of centers 

{ of stream outClientFile("pat003-centers. txt", ios::app); 
{ outClientFile « (k+1) « endl « setw(5) « "x" 
« setw(5) « "y" « setw(5) « "z" « setw(lO) 
« "radius" « endl « setw(5) « (xc[suprad[k]]-xf ix) 
« setw(5) « (yc[suprad[k]]-yfix) << setw(5) 
<< (zc[suprad[k]]-zfix) << setw(lO) << maxrad << endl; 
} 
} 

// remove the biggest sphere •' 

for (int p=0; p<nc; ++p) 

{ int dist = floor(sqrt( square (yc[suprad[k]]-yc[p]) 

+ square (xc[suprad[k]]-xc[p]) 
+ square (zc[suprad[k]]-zc[p]) )); 
if ( dist < maxrad ) 
tcc[p] =0; 
else; 
} 

// setting the remaining tumor cell by -2 
for (int i=0; i<nc; i++) 
{ if ( tcc[i] >= 1 ) 
tccLi] = -2; 



89 


'• ■- ,.■- .*-- . ,'. '..-■ ;- 


Jv">X ^ ■■ , - ^ 1^.^^^^ 


else; 


} 


// setting the boundary cells 


for (int j=0; j<=MAX(x,y,z)/2+l; j++) 


{ int 1=0; 


for (int i=0; i<nc; i++) 


■C if (tcc[i] == -2) 


{ if ( tcc[i-l] == j 1 1 tcc[i+l] ==j II tcc[i-y]==j 


II tcc[i+y]==j II tcc[i-y*x]==j I I tcc[i+y*x]==j ) 


{ tcc[i] = j + 1; 


++1; 


> 


else; 


} 


else; 


} 


if (1==0) 


break; 


else; 


} 


// check if there is more maxrad pixcel 


for (int i=0; i<nc; i++) 


{ if ( tcc[i] == maxrad ) 


{ cout << endl << endl << endl << 


" WARNING!!! WE HAVE MORE 'MAXRAD' PIXCEL AT (" 


« xc[i] « "," « yc[i] « "," « zc[i] « ")" « endl; 


cin >> q; 


break; 


} 


else; 


} ■ 


//remove the smaller nr- = funhf^r-f^ 



for (int j=maxrad-l; j>l; — j) 
{ for (int i=0; i<nc; ++i) 

{ if ( tcc[i] ==j ) . 

{ TotalNofBox4[j]++; 

// output the result of centers 

{ of stream outClientFile("pat003-centers .txt" , 

ios : :app) ; 
{ outClientFile « setw(5) « (xc[i]-xfix) 
« setw(5) «(yc[i]-yfix) « setw(5) 
« (zc[i]-zfix) << setw(lO) << i << endl; 
} 
. } 

// remove the sphere 
for (int 1=0; Knc; ++1) 

{ int dist = floor(sqrt( square (yc [i] -yc[l] ) 

+ square (xc[i]-xc[l]) 
+ square (zc[i]-zc[l]) )); 
if ( dist < j ) 

tcc[l] = 0; 







90 




else; 




} 






// 


setting the remaining tumor cell by -2 




for (int i=0; i<nc; i++) 




{ 


if ( tcc[i] >= 1 ) 

tcc[i] = -2; 
else; 




} 


* ^' .'.-., ■■> 




// 


setting the boundary cells 




for (int j=0; j<=MAX(x,y,z)/2+l ; 1++) 




{ 


int 1=0; 

for (int i=0; i<nc; i++) 

{ if (tcc[i] == -2) 

{ if ( tcc[i-l] == j II tcc[i+l] ==j II 
tcc[i-y]==j II tcc[i+y]==j || 
tcc[i-y*x]==j II tcc[i+y*x]==j ) 
{ tcc[i] = j + 1; 

++1; 
} 

else; 
} 

else; 
} 

if (1==0) 
break; 
else; 




} 






} 






else; 






} 






> 






{ of stream outClientFile("pat003-centers.txt", ios::app); 




{ outClientFile « endl ; 




} 






} 






} 






} 


- - 




int square (int a) 






{ return a*a; 






} 






int MAX(int a, int 


b, int c) 




{ int p=0; 






p = a; 






if (a<=b) 






P = b; 






else if (a<=c) 






p = c; 






else; 






return p; 











■ • '•-,.--■ , » < i \ ■•■ .■ > > I 



APPENDIX B 
PROGRAM FOR THE MAXIMAL TREE OF A GRAPH 

In this appendix, we provide the Mathematica program we developed in joint 
work with Matthew Harvey. The program below was written by Matthew Harvey to 
get the maximal tree for the graph which we assigned for a brain tumor. Note that 
this program does not use the method of ordering for the vertices as in Chapter 3. 
Instead this program uses some commands which are in the function package in the 
Mathematica program library. If anyone wants to develop a program like this using a 
different program language, we recommand the vertex ordering algorithm in Chapter 
3. 

<< DiscreteMath'Combinatorica' 
Off [General: : spell] 

LexPrecedes[a_, b_] := Module [{i}, 

For[i =1, i <= Min [Length [a] , Length [b] ] , i++, 
If[ a[[i]] != b[[i]], 

If[ a[[i]] > b[[i]], Return [True] , Return[False] ] ] 

]; 

If[ Length [b] > Length [a]. Return [False] ]; 
Return [True]] 

DegreePoint[a_, k_] := Count [Flatten [ToUnorderedPairs [a]] , k] ; 

IndSubgraph [Graph [g_, v_] , s.List] := Module [{i, j, newmat , sc}, 
newmat = g; 

sc = Complement [Range [Length [v]] , s] ; 
For[i = 1, i <= Length [g], i++, 
For[j = 1, j <= Length [g], j++, 

If [MemberQ[sc, i] || MemberQ[sc, j] , newmat[[i, j]] = 0]]]; 
Graph [newmat , v] ] ; ■ 

CutPoints[gr_] := 

Select [ArticulationVertices [gr] , DegreePoint [gr, #] > 2 &] 

NonCutPartitions[gr_] := Module [{partitions, cpts, bees, skeleton}, 

partitions = {}; 

bees = Select [BieonnectedComponents [gr] , Length [#] > 2 &] ; 

partitions = Union [partitions, bees] ; 

skeleton = 

IndSubgraph [gr , 
Union [ 

Complement [ Range [V[gr]] , Flatten [bees] ], 



91 



■ ] 

]; 



92 

CutPointsCgr] 



partitions = 

Union [partitions , 

Select [ConnectedComponents [ 
FromllnorderedPairs [ 

Select [ToUnorderedPairs [ 
skeleton] , # != 
Intersection[#, 
Flatten [ 

Select [BiconnectedComponents [skeleton] , 
Length [#] > 2 &] 
] 
] 
&] 
] 
], Length [#] > 1 
&] 

]; 

Table [ 

Select [ 

ToUnorderedPairs [gr] , 

# == Intersection[ #, partitions [[i]] ] 
&] , {i, Length[partitions]}]] 



'♦<->«; 



U'^ V. :^ ^ . , "■■■■■' ' ''>\A\ 



APPENDIX C 
PROGRAM FOR CLASSIFYING TREES BY SEQUENCES 

In the first section, we provide the Mathematica program we developed in 
joint work with Matthew Harvey. This program was written by Matthew Harvey to 
get the maximal degree sequences for any given integer n > 2. And we show the 
program results up to n = 10 in the second section. 

C.l Program 

Off [General: : spell] 

<< DiscreteMath'Combinatorica' 

DoPartitions[n_] := 
Module [{i, k, templist, returnlist}, 
If [n == 0, {{}}, 

returnlist = {}; 

ForCk = n, k >= 1, k— , 

templist = DoPartitionsEn - k] ; 
For[i = 1, i <= Dimensions [templist] [[1]] , i++, 
returnlist = Append [returnlist , 

Flatten[{k, templist [[i]]}] 
] 
] 

returnlist 

h 

i 

Filter [thelist_] := '•■'■■ -'- ^ .:./"• t '■ 
Select [thelist , 

! ( Memberq[{l, 2}, #1[[1]]] I I (Max[#l] != First[#l]) 
I I (Count [#1, Max[#l]] > 1) 
) 
ft] 

AddZerosToSeq[part_] := 

Module [{nZeros, n, i, j, k, sum, positions, seqs, withzeros}, 

If [Length [part] == 1, Return [{Table [If [i == 1, part[[l]], 0], 

{i, part[[l]] + 1}]}] 

Ir 

seqs = {}; 

sum = Sum [part [ [i] ] , {i, 1, Length [part] }] ; 

nZeros = (sum + 1) - Length [part] ; 

n = Table [k, {k, 3, sum}]; . . 

positions = KSubsets[n, nZeros -1]; 



93 



94 



] 



For[i = 1 , i <= Length [positions] , i++, 
k = 2; 

withzeros = {First [part] }; 
For[j = 2, j <= sum, j++, 

If [MemberQ [positions [[i]] , j] , 

withzeros = Append [withzeros, 0] , 
withzeros = Append [withzeros, part[[k]]]; 
k++ 
] 
]; 

withzeros = Append [withzeros, 0]; 
seqs = Append [seqs, withzeros] 

seqs 



AddZeros [seq_] := 

Flatten[Table[ AddZerosToSeq[seq[[i]]], {i, 1, Length [seq]} ], 1] 

SubSeqs [dseq_] := 

Module [ {branchlist, branch, workseq, branches, i}, 
branches = dseq[[l]] ; 
workseq = Drop[dseq, 1]; 
branchlist = {}; 
For[i =1, i <= branches, i++, 
dsum = workseq[[l]] ; 
workseq = Drop [workseq, 1]; 
branch = {dsum}; 

While [dsum != 0, dsum += (workseq [[1]] - 1); 
branch = Append [ branch, workseq [[1]] ]; 
workseq = Drop [workseq, 1] 

branchlist = Append [branchlist , branch] 

branchlist 
] 

LexPrecedes[a_, b_] := - - 

Module [{i}, 

For[i = 1, i <= Min [Length [a] , Length [b]], i++, 
If[a[[i]] != b[[i]], 

If[ a[[i]] > b[[i]], Return [True] , Return[False] 

] 

]; 

If [Length [b] > Length [a]. Return [False] ] ; 
Return [True] 
] 

WeightsQ[dseq_] := 

Module [{i, subseqs, flag}, 

subseqs = SubSeqs [dseq] ; 

flag =1; 

If [OrderedQ [subseqs, LexPrecedes] , 



95 



For[i =1, i <= Length [subseqs] , i++, 

If[ ! Weightsq [subseqs [[i]]] , flag=0, flag*=l ] 

Return [False] 

]; 

If[ flag == 1, Return [True] , Return [False] ] 
] 

DegreeSumQ[dseq_] := 
Module [{dsum}, 

dsum = dseq[[l]] ; 

For[i =2, i <= Length [dseq] , i++, 
dsum += dseq[[i]] - 1; 
If [dsum == 0, 

If[i == Length [dseq] , Return [True] , Return [False] 
] 
] 

]; 

Return [False] 
] 

ExtractSubtree[dseq_] := 
Module [{rtotal} , 

rtotal = dseq[[l]] ; 

i = 1; 

While [rtotal > 0,i++; 

rtotal += dseq[[i]] - 1; 

]; 

Take [dseq, i] 

RewriteTree[dseq_, i_] := 

Module [{branchesoff, subtree, brlength, seqlst}, 

If[i == 1, Return [dseq] ] ; 

branchesoff = i - 1; 

While [ ( branchesoff > 1 && Sum [dseq [[k]] - 1, 
{k, branchesoff, i - 1}] < ) I I 
dseq[[branchesoff]] == 0, branchesoff — ]; 

brlength = Length [ ExtractSubtree [Drop [dseq, i - 1]] ] ; 

subtree = Drop [dseq, {i, i + brlength - 1}]; 

subtree [ [branchesoff] ] — ; 

seqlst = SubSeqs [Take [dseq, {i, i + brlength - 1}]]; 

seqlst = Append [seqlst, RewriteTree[subtree,branchesoff]] ; 

seqlst = Sort [seqlst, LexPrecedes [#1 , #2] &] ; 

Flatten [{dseq[[i]] + 1, seqlst}] 

RightOrderQ[dseq_] := 

Module [{pos, seqs, j, rewritten}, 

pos = Flatten[ Position[dseq, dseq[[l]] - 1] ] ; 

If [pos == {}, Return [True] ] ; 

seqs = {}; 

For[j = 1, j <= Length [pos], j++, 

rewritten = RewriteTree[ dseq, pos[[j]] ]; 



96 



If [LexPrecedes [rewritten, dseq] && rewritten != dseq, 
Return [False] 

] -\l '\ 1 ' :>»•,.; '-,4 n 

]; 

Return[True] "lit-Ai N'T .. ? 

] "* ) . 

LemmasQ[dseq_] := . - -^ , 

DegreeSumQ[dseq] && WeightsQ [dseq] && RightOrderq[dseq] 

CheckLemmas [1 st seq_] : = 
Module [{retseq, twoseq, i, j, n, p}, 
retseq = {}; 
J = 0; 
P = 10; 

n = Length [Istseq] ; 
For[i = 1, i <= n, i++, 
If [ j > n/10, 

Print [p, '"/."]; 
P += 10; 
j = 

]; 

If[LenmiasQ[ lstseq[[i]] ], 

retseq = Append[ retseq, lstseq[[i]] ] 

]; 

twoseq = {2}; 

If [Length [Istseq] > 0, 

For[i = 2, i < Length [ retseq [[1]] ] - 1, i++, 
twoseq = Append [twoseq, 1] 

]; 

twoseq = Join[twoseq, {0, 0}]; 
retseq = Append [retseq, twoseq] ; 
retseq 

DSTRecursive[dseq_, bvert_, hvert_ , trparam. ] := 
Module [{i, v, tree, tempseq}, 
V = hvert ; 
tree = trparam; 

If [dseq != {0}, tempseq = Drop[dseq, 1]; 
For[i = 1, i <= dseq[[l]], i++, 
V++; 

tree = Append [tree, {bvert , v}] ; 
subseq = ExtractSubtree [tempseq] ; 
tempseq = Drop[tempseq, Length [subseq] ] ; 
{tree, v} = DSTRecursive [subseq, v, v, tree]; 

J > 
]; 
{tree, v} 



97 



DegreeSeqToTree[dseq_] := 

First [ DSTRecursiveidseq, 1, 1, {}] ]; 

ToGraphics[ckd_] := 
For[t = 1, t <= Length [ckd], t++, 
Print [ckd[[t]]]; 

ShowGraph [Radial Embedding [FromUnorderedPairs 
[ DegreeSeqToTree[ckd[[t]]] ] 
] 

3 
3 

C.2 Some Program Results 

The notation for a degree sequence is {di,d2, . . . ,dn) . But the Mathematica 
program produces the sequence notation with { and }. So in this section, any set 
notation is actually denotes the degree sequence. Note that an n-tree has n vertices, 
so there are n-1 edges. 



n=3 
{2, 0, 0> 



total 



n=4 
{3, 0, 0, 0}, 



total : 2 

{2, 1, 0, 0} 



n=5 total : 3 ■ '^ "■' " ' _ ' :'* 

{4, 0, 0, 0, 0}, {3, 1, 0, 0, 0}, {2, 1, 1. 0, 0} 





98 



n=6 



total 



{5, 0, 0, 0, 0, 0}, {4, 1, 0, 0, 0, 0}, {3, 2, 0, 0, 0, 0}, 
{3, 1, 0, 1, 0, 0}, {3, 1, 1. 0, 0, 0}, {2, 1, 1, 1, 0, 0} 






n=7 



total 



11 



{6, 0, 0, 0, 0, 0, 0}, {5, 1, 0, 0, 0, 0, O}, {4, 2, 0, 0, 0, 0, 0}, 

{4. 1, 0, 1, 0, 0, 0}. {4, 1, 1, 0, 0, 0, 0}, {3, 2, 1, 0, 0, 0, 0}, 

{3, 1, 2, 0, 0, 0, 0}, {3, 1, 0, 1, 0, 1, 0}, {3, 1, 1, 0, 1, 0, 0}, 

{3, 1, 1, 1, 0, 0, 0}, {2, 1, 1, 1, 1, 0, 0} 





fn'^ORJV 



\CP i</H- f jt^h.\ 





Vt if I 



99 



n=8 

■C7, 0. 0, 

{5, 2, 0, 

{5, 1, 1, 

{4, 2, 0, 

{4, 1, 2, 

{4. 1, 1, 

{3, 2, 2, 

{3, 2, 1, 

{3, 1, 2, 1 

{3, 1, 1, 

■C3, 1, 1, 1 

{2, 1, 1, 1 



, 0, 


0, 


, 0, 


0, 


, 0, 


0. 




0. 




0. 




0, 




0, 




0, 




0, 




0, 




1, 




1, 



total : 23 

0, 0}, {6, 1, 0, 0, 0, 

0, 0}, {5, 1, 0, 1, 0, 

0, 0}. {4, 3, 0, 0, 0, 

0, 0}, {4, 2, 1, 0, 0, 

0, 0}, {4, 1, 0, 1, 0, 

0, 0}, {4, 1, 1, 1, 0, 

0, 0}, {3, 2, 1, 0, 0, 

0, 0}, {3, 2, 1, 1, 0. 

0, 0}. {3, 1, 1, 2, 0, 

1, 0}, {3, 1, 1, 0, 1, 
0, 0}, {3, 1, 1, 1, 1, 
0, 0} 



0, 0, 0}, 

0, 0, 0}, 

0, 0, 0}, 

0, 0, 0}, 

1. 0, 0}, 

0, 0, 0}, 

1, 0, 0}, 
0, 0, 0}, 

0, 0, 0}, 

1, 0, 0}, 
0. 0, 0}, 











100 



n=9 



total : 47 



{8 
{6 
{6 
{5 
{5 
{5 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{2 



, 


, 


, 


, 


. 


, 


, 0, 


0} 


, il 


, 1 


, 


, 


, 


, 


, 


, 0. 


, 2 


, 


, 


, 


, 


, 


, 0, 


0} 


, {6 


, 1 


, 


, 1 


. 


. 


, 


, 0. 


, 1 


, 1 


, 


, 


, 


, 


, 0, 


0} 


, {5 


, 3 


, 


, 


, 


, 


, 


, 0. 


, 2 


, 


, 


, 1 


, 


, 


, 0, 


0} 


, {5 


2 


, 1 


, 


, 


, 


, 


, 0, 


, 1 


, 2 


, 


, 


, 


, 


. 0, 


0} 


. {5 


1 


, 


, 1 


, 


, 1 


, 


. 0, 


, 1 


, 1 


, 


, 1 


. 


, 


, 0, 


0} 


, {5 


1 


, 1 


, 1 


, 


, 


, 


, 0, 


, 3 


, 1 


, 


, 


. 


, 


, 0, 


0} 


{4 


2 


, 


, 


, 2 


, 


, 


0. 


, 2 


, 2 


, 


, 


, 


, 


, 0, 


0} 


{4 


2 


, 


, 


, 1 


, 


, 1 


0. 


, 2 








1 


, 1 


. 


. 0. 


0} 


{4 


2 


1 


> 


, 


1 


, 


0, 


, 2 


1 





1 


, 


, 


, 0, 


0} 


{4 


2 


1 


1 


> 





, 


0, 


. 1 


3 














0, 


0} 


{4 


1 


2 








1 





0. 


, 1 


2 













0, 


0} 


{4 


1 


1 


2 











0, 


, 1 










1 





1, 


0} 


{4 


1 


1 





1 





1 


0, 


. 1 


1 




1 


1 





0, 


0} 


{4 


1 


1 


1 





1 





0, 


, 1 


1 




1 








0, 


0} 


{3 


2 


2 








1 





0. 


, 2 


2 













0, 


0} 


{3, 


2 


1 


2 








0, 


0. 


, 2 


1 




1 





1 


0. 


0}, 


{3, 


2 


1 


1 








1, 


0, 


. 2 


1 







1 





0, 


0}, 


{3, 


2 


1 


1 


1 





0, 


0, 


, 1. 


2, 










1 


0, 


0}, 


{3, 




2 


1 


0, 


1 


0, 


0. 


, 1. 


2, 




1, 


0, 


0, 


0, 


0}, 


{3, 




1, 


2 


1, 





0, 


0, 


, 1, 


1, 




2, 


0: 


0, 


0, 


0}, 


{3, 




1, 


0, 


1, 


1, 


0, 


1, 


, 1, 


1, 




0, 


1, 


0, 


1, 


0}, 


{3, 




1, 


1, 


0, 


1, 


1, 


0, 


, 1, 


1, 




1, 


0, 


1, 


0, 


0}, 


{3, 




1, 


1, 


1, 


1, 


0, 


0, 


. 1, 


1, 




1, 


1, 


1, 


0, 


0} 



















0}. 
0}. 
0}. 

o>, 

0}, 
0}, 
0}. 
0}. 
0}. 
0}, 
0}. 
0}. 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}. 
0}. 
0}, 
0}, 
0}, 





n 


= 10 








total 


: 106 






















{9, 


0, 


0. 


0. 


0, 


0, 


0, 


0, 


0, 


0}, 


{8, 


1. 


0, 


0, 


0, 


0, 


0, 


0, 


0, 


0}, 


{7. 


2, 


0, 


0, 


0, 


0, 


0, 


0, 


0, 


0}. 


{7, 


1, 


0, 


1, 


0, 


0, 


0, 


0, 


0, 


0}. 


{7, 


1, 


1, 


0, 


0, 


0, 


0, 


0, 


0, 


0}, 


{6. 


3, 


0, 


0, 


0. 


0, 


0, 


0, 


0, 


o>, 


{6, 


2, 


0, 


0, 


1, 


0. 


0, 


0. 


0, 


o>. 


{6. 


2, 


1. 


0, 


0. 


0. 


0. 


0, 


0, 


0}. 


{6, 


1. 


2. 


0, 


0, 


0, 


0, 


0, 


0, 


0}, 


{6. 


1. 


0, 


1. 


0, 


1, 


0. 


0, 


0, 


0}, 


{6, 


1, 


1, 


0, 


1, 


0. 


0, 


0, 


0, 


0}, 


{6, 


1. 


1, 


1, 


0, 


0. 


0, 


0, 


0, 


0}, 


■C5. 


4, 


0, 


0, 


0, 


0, 


0. 


0, 


0. 


o>. 


{5, 


3, 


0, 


0, 


0, 


1, 


0. 


0, 


0, 


0}. 


{5, 


3. 


1. 


0. 


0, 


0, 


0. 


0, 


0, 


0}. 


{5, 


2. 


0, 


0, 


2, 


0. 


0, 


0, 


0, 


0}, 


{5, 


2, 


2, 


0, 


0, 


0, 


0. 


0, 


0. 


0}. 


{5. 


2, 


0, 


0, 


1. 


0, 


1, 


0, 


0, 


0}, 


{5, 


2, 


0. 


0, 


1, 


1, 


0, 


0, 


0. 


0}, 


{5, 


2. 


1, 


0. 


0, 


1, 


0, 


0, 


0, 


0}. 


{5, 


2, 


1, 


0, 


1, 


0, 


0. 


0, 


0, 


0}. 


{5, 


2, 


1, 


1, 


0, 


0, 


0, 


0, 


0, 


0}. 


{5, 


-'- > 


3, 


0, 


0, 


0, 


0, 


0, 


0, 


0}, 


{5. 


1, 


2, 


0, 


0, 


1, 


0, 


0, 


0, 


o>. 


{5, 


■^ > 


2, 


1, 


0, 


0. 


0, 


0, 


0, 


0}, 


{5, 


1, 


1, 


2, 


0. 


0, 


0, 


0, 


0, 


o>, 


{5, 


-^ » 


0. 


1, 


0, 


1, 


0, 


1, 


0, 


0}. 


{5. 


1, 


1, 


0. 


1, 


0, 


1, 


0, 


0, 


o>. 


{5, 


-'- > 


1, 


0, 


1, 


1, 


0. 


0. 


0. 


0}, 


{5, 


1, 


1, 


1, 


0, 


1. 


0. 


0, 


0, 


0}, 


■C5. 


■'- > 


1, 


1, 


1, 


0, 


0, 


0, 


0. 


0}, 


{4. 


3, 


2, 


0, 


0, 


0, 


0, 


0. 


0, 


0}. 


{4, 


3, 


1, 


0, 


0, 


0. 


1. 


0. 


0. 


0}. 


{4, 


3, 


1, 


0, 


1, 


0, 


0, 


0, 


0, 


0}, 


{4, 


3. 


1. 


1, 


0, 


0, 


0, 


0, 


0, 


0}, 


{4, 


2. 


3, 


0, 


0. 


0, 


0, 


0, 


0, 


0}, 


{4, 


2, 


0, 


0, 


2, 


0, 


0. 


1, 


0, 


o>. 


{4, 


2, 


2, 


0, 


0, 


0, 


1. 


0, 


0, 


0}, 


{4, 


2, 


2. 


0, 


0, 


1, 


0. 


0, 


0, 


0}, 


{4, 


2, 


2, 


1, 


0, 


0, 


0, 


0, 


0, 


0}. 


{4, 


2, 


0, 


0, 


1, 


2, 


0, 


0, 


0, 


0}. 


{4, 


2, 


1, 


0, 


0. 


2, 


0, 


0, 


0, 


0}, 


{4. 


2. 


1, 


2. 


0, 


0, 


0, 


0, 


0, 


0}, 


{4, 


2, 


0, 


0. 


1, 


0, 


1, 


0, 


1, 


0}, 


{4, 


2, 


0, 


0, 


1, 


1, 


0. 


1. 


0, 


o>. 


{4. 


2, 


0, 


0, 


1. 


1, 


1, 


0, 


0. 


0}, 



101 



{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
■C3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 



, 2 


, 1 


, 


, 


, 1 


. 


, 1 


, 0, 


, 2 


, 1 


, 


, 1 


, 


, 1 


, 


, 0, 


, 2 


, 1 




, 


, 1 


, 


, 


0, 




, 3 




, 


, 


, 





0, 




, 2 




, 


, 1 


, 


1 


0, 




, 2 




, 


, 


, 1 





0, 




, 2 




, 1 


. 


, 





0, 




, 1 




, 


, 


, 1 





0, 




, 1 




, 2 


, 


, 





0, 




, 1 




, 1 


, 1 


, 


1 


0. 




, 1 




, 


, 1 


, 1 





0, 




, 1 




, 1 


, 1 


, 





0, 


', 2 


2 




, 


, 


, 





0, 


, 2 


2 




, 


, 


, 


1 


0, 


, 2 


2 




. 


, 1 


, 





0, 


, 2 


1 


2 











1 


0, 


, 2 


1 


2 


1 











0, 


, 2 


1 





1 





1 





1, 


, 2 


1 


1 








1 


1 


0, 


, 2 


1 


1 





1 


1 





0, 


, 2 


1 


1 


1 





1 





0. 




2 


1 


2 











0, 




2 


1 


1 








1 


0. 




2 


1 


1 


1 








0, 




1 


2 


1 





1 





0, 




1 


1 


2 


1 








0, 




1 





1 


1 


0, 


1 


1. 




1 


1 





1 


1, 


1, 


0, 


y ^ i 


1. 


1 


1 





1, 


1 = 


0, 


f -^ i 


1. 


1 = 


1, 


1, 


1, 


0, 


0. 



0}. 
0}. 
0}. 
0}. 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}. 
0}. 
0}. 
0}. 
0}, 
0}, 
0}, 
0}. 
0}, 
0}, 
0}, 
0}, 
0}, 

o>. 

0}. 

0}. 
0}. 



{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{4 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{3 
{2 



, 2 


, 1 


, 


, 


, 1 


1 


, 


, 0. 


, 2 


, 1 


, 1 


, 


, 


, 1 


, 


. 0, 


, 2 


, 1 


, 1 


, 1 


, 


, 


, 


, 0, 




. 2 


, 2 


, 


, 





, 


, 0, 




, 2 


, 


, 


, 1 


, 1 


, 


, 0, 




, 2 


, 1 


. 


, 1 





, 


, 0, 






, 3 


. 


, 


, 


, 


, 0. 






, 2 


, 1 





, 


, 


, 0, 






, 


, 1 





1 


, 


, 1, 






, 1 


, 


1 





, 1 


, 0, 






, 1 


, 1 





1 


, 


. 0, 


', 2 


', 2 


, 


, 


2 





, 


, 0, 


, 2 


, 2 


, 


, 


1 


1 


, 


. 0, 


, 2 


2 


, 1 








1 


, 


. 0, 


, 2 


2 


, 1 


1 








, 


, 0, 


, 2 


1 


2 








1 





0, 


, 2 


1 


1 


2 











0. 


, 2 


1 


1 








1 





1, 


, 2 


1 


1 





1 





1 


0, 


, 2 


1 


1 


1 








1 


0, 


, 2 


1 


1 


1 


1 








0, 




2 


1 





1 





1 


0. 




2 


1 


1 





1 





0, 


y ■*■ 


1 


2 


1 








1 


0, 


y -*■ 


1 


2 


1 


1 








0, 


J -'■ 


1 


1 


1 


2 








0, 


» ^ 


1 


1 


0, 


1, 


1 





1, 


y ■*■ 


1 


1 


1, 





1 





1. 


y ^ 


1 


1 


1, 


1, 





1, 


0, 


y -'• i 


1, 


1 = 


1, 


1, 


1. 


1> 


0, 



0}, 
0}, 
0}. 
0}. 
0}, 
0}, 
0}, 
0}. 
0}, 

o>, 

0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 
0}, 

o>. 

0}. 
0}, 
0}, 
0}, 
0}. 
0}. 
0} 



-end of data- 



APPENDIX D 
LABELED GRAPHS AND TREES 

D.l Number of Labeled Graphs and Labeled Trees 

To obtain the number of labeled graphs with n vertices, we need only observe 
that each of the (2) possible edges is either present or absent. Thus we have the 
following theorem: 

Theorem D.1.1 [5] The number of graphs on n labeled vertices is 2^^K 

In Lovasz [6], the Priifer-code is used to denote a labeled tree. And, for any 
given Priifer-code, one can construct the tree which is denoted by that code. Then, 
using the properties of the Priifer-code, Cayley proved the following theorem: 

Theorem D.l. 2 (Cayley) [8] The number of trees on n labeled vertices is n"~^. 

D.2 Sketch of the Construction of a Priifer-code 

Among the end vertices of a given labeled tree, pick the one whose label is 
minimal. Cut it off from the tree and write down the label of its adjacent vertex. 
Repeat this process until only one edge remain. At this point we have a sequence of 
n — 1 numbers written down. We call this resulting sequence the Priifer-code of the 
tree. 

The following example shows how we construct the Priifer-code of a given 
tree. 

Example D.2.1 Let T be the tree shown below. 

-3,6 



Figure D-1. 
. ' '■ * ' • -^ 

There are 5 end vertices, 2, 3, 4, 6, 8. We cut off the smallest labeled end vertex 
which is 2. Then the sequence is (1) and the remaining tree is Figure D-2 below. 

Then we cut off the next smallest labeled end vertex which is 3, and add the 
label, 1, of the adjacent vertex of 3 to the sequence. That is, the sequence is (1, 1) . 
From the remaining tree we cut off the next smallest labeled end vertex which is 4. 
Then the sequence is (1,1,1). And we get the tree shape in Figure D-3. 



102 



V"^ 



103 



".if.. * .-. 
• 3 *' ,6 






Figure D-2. 
f6 



15 7 8 

. , ^ Figure D-3. 

Among the 3 end vertices, 1 is the smallest labeled one. So we cut off the 
vertex 1 and write down the label, 5, of the adjacent vertex of 1. The sequence then 
will be (1, 1, 1,5) and the remaining tree is Figure D-4. 

• 6 



5 7 8 

Figure D-4. 

The remaining tree has two end vertices, that is, it is a linear shape. We cut 
off the smaller labeled vertex, 6. And the sequence will be (1, 1, 1, 5, 5) . After we cut 
off the next smaller labeled vertex which is 5, and get the sequence (1, 1, 1, 5, 5, 7) , 
the remaining tree has only two vertices. It's clear we have to cut off the smaller 
labeled vertex which is 7 and the adjacent vertex will be 8. Therefore we do not need 
to add this number to the sequence. Hence the last sequence, (1, 1,1,5, 5, 7) , is the 
Priifer-code of the given tree T. 

If we assign different labels for the tree above, then we will get a different 
Priifer-code. But the code must consist of 6 terms which is two less than the total 
number of vertices in the tree. And each term can be any number among 1, 2, . . . , 8. 
Thus we have the following theorem. 

D.3 Reconstruction of a Tree from a Priifer-code 

Let (ai,a2,...,a„_2) be a Priifer-code. That is, we expect an n-tree. Let 
bi,b2,. . . ,bn-i be the indices of the removed points. Then, for any ?, 6, is obviously 
different from 61,62, ... ,6,_i,ai. Also, 6, / a^ if j > i, because 6, is removed in 
the i-th step, so it can not be an adjacent vertex later. 

Conversely, if A; ^ {6i, 62, . . . , 6._i, a„ a,+i, . . . , a„_2}, then Vk is an end ver- 
tex of V{T)-{vk,,Vk,,...,vt,_,}. Thus 



104 



bi - mm{k\k ^ {61,62, ... ,6i_i, ai,a,.,.i, .. . ,0^-2}- 

Let the sequence (1,1,1,5,5,7) be a Prufer-code. That is, ai = 1,02 = 
1,03 = 1,04 := 5, as = 5,06 = 7. Then 61 = imn{k\k ^ {01,02, ••• ,06}} = 
min{/i;|A; {1,5,7}} = min{2,3,4,6,8} = 2. That is, there is an edge between oi = 
1 and 61 = 2. Then 62 = min{A;|A; ^ {61,02, ... ,06}} = min{fc|A; ^ {2,1,5,7}} = 
min{3,4,6,8} = 3. Thus the tree T has an edge between 02 = 1 and 62 = 3. In a 
similar manner, we have the following: 

63 = min{A;|/c ^ {61,62,03, ...,06}} 

= min{A;|^- ^ {2, 3, 1, 5, 7}} = min{4, 6, 8} = 4, 
(Thus T has an edge {03,63} = {1,4}) 

64 = min{/i;|A; ^ {61,62,63,04,05,05}} 

= min{A;|A; ^ {2,3,4,5,7}} = min{l, 6,8} = 1, 
* (Thus T has an edge {04,64} =: {5,1}) 

65 = min{A;|A: ^ {61,62,63,64,05,06}} 

= min{A;|A; ^ {2, 3, 4, 1, 5, 7}} = min{6, 8} = 6, 
(Thus T has an edge {05,65} = {5,6}) 
65 = min{A;|A; ^ {61,62,63,64,65,06}} 

= min{A;|A; {2, 3, 4, 6, 7}} = min{5, 8} = 5, 
(Thus T has an edge {05,66} — {7,5}). 

And, for the vertex 05 = 7, the largest labeled vertex vs will be the remaining 
adjacent vertex, that is, there is an edge {7,8}. 

So the tree T has the vertex set V = {1,2,3,4,5,6,7,8} and the edge set 
£ = {{1, 2}, {1, 3}, {1,4}, {1,5}, {5, 6}, {5, 7}, {7, 8}}, which is the tree shape in the 
example above. That is, we can construct a labeled tree from a Priifer-code. Clearly, 
different Priifer-codes produce different labeled trees. 



BIOGRAPHICAL SKETCH 



Tae-Il Yi was born December 16, 1962 in Seoul, Korea. He attended the 
Dankook University from 1981 to 1988, earning a Bachelor of Science degree in math- 
ematics education in February 1988. During college, he was in the service of the 
Korean Army for 27 months. After college, he entered graduate school at Dankook 
University in March 1988, and completed a Master of Science degree in mathemat- 
ics in Feburary 1990. During that time he worked at Yongmoon High School as a 
mathematics teacher. 

He married Moon-Sil Kim on June 27, 1987. Their first son, Han-Yong 
(David), was born April 12, 1988, and their second son, Chang- Yong (Peter), was 
born May 3, 1994. 

In August 1991 Tae-Il Yi entered graduate school in the Mathematics De- 
partment at the University of Illinois at Urbana/Champaign. After receiving the 
degree of Master of Science in August 1994, he moved to graduate school in the In- 
struction and Curriculum Department of the College of Education at the University 
of Florida, and in August 1995 transfered to the University of Florida, Mathematics 
Department. He pursued a concurent degree in the College of Education and received 
a degree of Master of Education in December 1997. During his doctoral work in the 
Mathematics Department, he served as a graduate teaching assistant. 

He received a Russell Corporation Endowed Dissertation Scholarship Spring 
2000. He is a member of the Phi Kappa Phi honor society. 



105 



I certify that I have read this study and that in my opinion it conforms to 
acceptable standards of scholarly presentation and is fully adequate, in scope and 
quality, as a dissertation for the degree of Doctor of Philosophy. 




Beverly L.-^rechner, Chairman 
Professor of Mathematics 

I certify that I have read this study and that in my opinion it conforms to 
acceptable standards of scholarly presentation and is fully adequate, in scope and 
quality, as a dissertation for the degree of Doctor of Philosophy. 




'hilip Boyland 
Associate Professor of Mathematics 

I certify that I have read this study and that in niy opinion it conforms to 
acceptable standards of scholarly presentation and is ffillif adequate, in scope and 
quality, as a dissertation for the degree of Doctor of Phi^o^ophj^ 



JLames E. Kefeling / 

"^rofessor of Mathematic^ 

I certify that I have read this study and that in my opinion it conforms to 
acceptable standards of scholarly presentation and is fully adequate, in scope and 
quality, as a dissertation for the degree of Doctor of Philosophy. 



lev, 



Li-Chien Shen 

Professor of Mathematics 

I certify that I have read this study and that in my opinion it conforms to 
acceptable standards of scholarly presentation and is fully adequate, in scope and 
quality, as a dissertation for the degree of Doctor of Philosophy. 




Mary G. Kanxowski 

Professor of Teaching and Learning 

This dissertation was submitted to the Graduate Faculty of the Department of 
Mathematics in the College of Liberal Arts and Sciences and to the Graduate School 
and was accepted as partial fulfillment of the requirements for the degree of Doctor 
of Philosophy. 

August 2000 



Dean, Graduate School 




UNIVERSITY OF FLORIDA 



3 1262 08555 1710